Score : 700 points
We have N gemstones labeled 1 through N.
You can perform the following operation any number of times (possibly zero).
Then, for each i, if the gem labeled i remains without getting smashed, you will receive a_i yen (the currency of Japan). However, a_i may be negative, in which case you will be charged money.
By optimally performing the operation, how much yen can you earn?
Input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Print the maximum amount of money that can be earned.
6 1 2 -6 4 5 3
12
It is optimal to smash Gem 3 and 6.
6 100 -100 -100 -100 100 -100
200
5 -1 -2 -3 -4 -5
0
It is optimal to smash all the gems.
2 -1000 100000
99000