D. Masha and Gleb are Moving
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Masha and Gleb decided to move to city M and are considering purchasing land there. There are a total of $$$n$$$ plots of land for sale, located consecutively along the road. The price of each plot is known. Some prices may even be negative — in such cases, the city is willing to pay the buyer just to relieve itself of the responsibilities of maintaining problematic plots.

Masha wants to choose one or several plots that are necessarily consecutive so that they can be merged into one. Gleb wants to do the same. Additionally, Masha and Gleb want to be neighbors — that is, after merging, their combined plots must be adjacent.

Gleb is very lazy, so he asked Masha to select the plots for both of them. Masha, tired of Gleb's laziness, decided to teach him a lesson and choose the plots in such a way that the difference in the total costs of Gleb's plots and Masha's plots is as large as possible. Write a program to find this maximum difference.

Input

The first line contains the number $$$n$$$ $$$(2 \le n \le 10^5)$$$. The next $$$n$$$ lines contain the numbers $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$ — the prices of the plots ($$$-10^9 \le a_i \le 10^9)$$$.

Output

Output a single integer — the maximum possible difference in the total costs of Gleb's plots and Masha's plots.

Scoring

Solutions that work correctly for $$$n \le 10$$$ will score at least 15 points. Solutions that work correctly for $$$n \le 200$$$ will score at least 30 points. Solutions that work correctly for $$$n \le 3000$$$ will score at least 60 points.

Examples
Input
3
1
2
3
Output
4
Input
7
1
2
-3
6
10
5
-100
Output
121
Note

Note that the answer may exceed the possible value of a 32-bit integer variable. Therefore, it is necessary to use a 64-bit integer data type (type int64 in Pascal, type long long in C++, type long in Java and C#). In Python, no additional actions are required.

Compiler Choice. If you are submitting a solution to this problem in Python, do not forget about the option to choose the pypy compiler — using it may significantly speed up your program.