새치기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 학생이 앞에 서거나 뒤에 설 때 얻을 수 있는 만족도 합의 최댓값을 구합니다.

난이도: 보통10점 중 4점
유형: 누적 합, 그리디, 배열
정답자: 아직 제출이 없습니다

문제

오늘 참슬기식당의 점심 메뉴는 치킨마요덮밥이다. 그래서 그런지 평소보다 훨씬 많은 학생이 줄을 선다. 학생들은 $1$ 번부터 $N$ 번까지 번호표를 가지고 있다. 학생들은 번호표 순서대로 줄을 서려고 한다. $1$ 번 번호표를 가진 학생은 줄에 처음 서며, 이때 만족도는 $s\_1$ 이다. $2$ 번 학생부터는 다음 두 가지 행동 중 하나를 선택해 줄을 선다.

맨 앞에 서기: 줄의 맨 앞에 서며, 이때 $i$ 번 학생의 만족도는 $s\_i$ 이다.
맨 뒤에 서기: 줄의 맨 뒤에 서며, 이때 $i$ 번 학생의 만족도는 $0$ 이다.

줄을 서는 방법에 따라 이미 줄에 있던 학생의 만족도도 바뀔 수 있다.

$i$ $i$ 번 학생 앞에 $j$ $j$ $(j > i)$ $(j > i)$ 번 학생이 있으면 $i$ $i$ 번 학생은 새치기를 당한 것이므로, 만족도가 $-s\_i$ $- s_i$ 로 바뀐다.
- 기존 만족도가 $0$ 이었더라도 $-s\_i$ 로 바뀔 수 있다는 점에 유의하라.
$i$ 번 학생 앞에 $j$ $(j > i)$ 번 학생이 없으면 $i$ 번 학생은 새치기를 당하지 않은 것이므로, 만족도는 변하지 않는다.

입력

첫 번째 줄에 학생의 수 $N$ 이 주어진다.

두 번째 줄에 양의 정수 $s\_1$ , $s\_2$ , $s\_3$ , $\cdots$ , $s\_N$ 이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 만족도 총합의 최댓값을 출력한다.

제한

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

예제3

예제 1
입력
```
2
1 10
```
예상 출력
```
9
```
예제 2
입력
```
3
10 1 1
```
예상 출력
```
10
```
예제 3
입력
```
4
1 2 4 1
```
예상 출력
```
1
```