Cutting in Line

Interview

Time limit1sMemory limit1024 MB

Summary

Given each student's satisfaction, find the maximum total when each student either cuts to the front or joins the back of the line.

Level: Medium4 of 10
Topics: Prefix sum, Greedy, Array
Solved: No attempts yet

Problem

Today the lunch menu at Chamseulgi Cafeteria is chicken mayo rice bowl. Perhaps because of that, far more students than usual are lining up. Students have ticket numbers from $1$ to $N$ . They line up in ticket order. The student with ticket $1$ joins the line first, and their satisfaction is $s\_1$ . Starting from ticket $2$ , each student chooses one of the following two actions.

Stand at the front: The student stands at the front of the line, and student $i$ has satisfaction $s\_i$ .
Stand at the back: The student stands at the back of the line, and student $i$ has satisfaction $0$ .

The way students line up can also change the satisfaction of students already in line.

If student $j$ $j$ $(j > i)$ $(j > i)$ is in front of student $i$ $i$ , student $i$ $i$ has been cut in front of, so student $i$ $i$ 's satisfaction changes to $-s\_i$ $- s_i$ .
- Note that it can change to $-s\_i$ even if the existing satisfaction was $0$ .
If no student $j$ $(j > i)$ is in front of student $i$ , student $i$ has not been cut in front of, so student $i$ 's satisfaction does not change.

Input

The first line contains the number of students $N$ .

The second line contains positive integers $s\_1$ , $s\_2$ , $s\_3$ , $\cdots$ , $s\_N$ , separated by spaces.

Output

Print the maximum possible total satisfaction on the first line.

Constraints

$1 \le N \le 100\,000$
$1 \le s\_i \le 10^9$
$1 \le i \le N$

Examples3

Example 1
Input
```
2
1 10
```
Expected output
```
9
```
Example 2
Input
```
3
10 1 1
```
Expected output
```
10
```
Example 3
Input
```
4
1 2 4 1
```
Expected output
```
1
```