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. 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≤ n ≤ 10⁵)

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

Output

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

Example

Input:
6
3 1 3 3 2 2

Output:
6