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 \leq n \leq 10^5~)
• The next line contains ~n~ integers ~k_i~ (~1 \leq i \leq n~ , ~|k| \leq 10^9~) -value of each tree.

Output

• Print the maximum value he can get.

Example Input 1

9
3 1 3 -8 3 -2 2 -1 3

Example Output 1

12