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~. Leo is about to get married, so he wants to choose some cut trees to sell for money. But he is a person who loves nature very much, he does not want to destroy all the forests, so he complies with ~2~ conditions:

• Cut down at most one of three consecutive trees
• There are some trees of the rare species with the value ~k < 0~, if the Beo is cut down, he will be fined a mount of money which is equal the absolute value of that tree. Calculate the maximum amount of money Beo can earn.

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

• A single integer, the maximum amount that Beo can get.

Example Input 1

6
3 1 3 3 2 2

Example Output 1

6