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