Recently I came across a task from Polish Informatics Olympiad called "Fence" and I can't solve it.
The first input line contains integer number n (1 <= n <= 200 000) and the second line contains n numbers (each is not less than 1 and not greater than 10^6). You have to delete some numbers so that the sum of the remaining ones is as large as possible and the their values have to increase and decrease. I mean, if A is a set of remaining numbers and ai is i-th number from set then a1 < a2 > a3 < a4 > a5 < a6 etc. or a1 > a2 < a3 > a4 < a5 > a6 etc.
From range of n values, it seems that the complexity of solution would be similar to O(n log n), but I'm not sure about that. I'd be grateful if someone told me the solution.
Some examples
Input:
2
100 90
Output:
190
Input:
6
7 5 4 6 6 5
Output:
23