Dorian challenges Koi with a puzzle, called "Number removal": Koi is given an array of \(n\) elements, he can remove some elements from the given array. Koi has to find which is the smallest sum obtainable from the remaining elements.

To prevent Koi gets the smallest sum by removing all positive numbers, Dorian adds another constraint: two consecutive elements can't be erased.

Fellow coders, please help Koi solve this puzzle.

Input

The first line of the input contains integer \(n\) \((1 \le n \le 2*10^5)\).

The second line contains \(n\) integers \(a_1, a_2, ..., a_n\) \((|a_i| \le 10^9)\) - the array elements.

Output

A single integer - the answer to Dorian's puzzle.

Example

Input 1:

10
1 2 3 4 5 6 7 8 9 10

Output 1:

25

Explaination: Koi removes all even integers from \(2\) to \(10\) to obtain the minimum sum.

Input 2:

5
1 -6 5 9 -8

Output 2:

-9

Explaination: Koi removes \(1\) and \(9\) to obtain the minimum sum.