EIU Programming Practices and Exams

There is a row of precious timber forests of n trees numbered from 1 to n and each tree has a monetary value of k. Phuc wants to cut some trees to get the maximum values and with the following conditions:

• Always cut at least two consecutive trees. It means that if you cut a tree, at least one of the next or the previous trees must be cut.
• There are some trees of the rare species with the value k < 0, if the Beo is cut down, he will be fined an amount of money that is equal to the absolute value of that tree.

Input

The first line contains a single integer n (1≤ n ≤ 10⁵)
The next line contains n integers ki (1≤ i ≤ n , |k| ≤ 10⁹) -value of each tree.

Output

Print the maximum value he can get.

Sample