32173번 - 새치기

문제

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

• 맨 앞에 서기: 줄의 맨 앞에 서게 되고, 이때 $i$번 학생의 만족도는 $s_i$이다.
• 맨 뒤에 서기: 줄의 맨 뒤에 서게 되고, 이때 $i$번 학생의 만족도는 0ドル$이다.

또한 줄을 서는 방법에 따라 기존 학생의 만족도가 변화할 수 있다.

• 만약 $i$번 학생 앞에 $j$ $(j > i)$번 학생이 있다면 새치기를 당했기 때문에 $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$

힌트