Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIULOGGING2 - LOGGING 2

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 ≤ 105)

The next line contains n integers ki (1≤ i ≤ n , |k| ≤ 109) -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

Added by:Ha Minh Ngoc
Date:2017-01-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.