A - Operations on a Stack Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ N の整数列 (A_1, A_2, \ldots, A_N) が与えられます。 また、列 S があり、S ははじめは空列です。

i = 1, 2, \ldots, N の順に、それぞれの i について、下記の 2 つの操作のうちちょうど 1 つを行います。

  • S の末尾に A_i を要素として追加する。
  • S の末尾の要素を削除する。ただし S が空のときは、この操作を行うことを選択できない。

すべての操作を終えた後の、S の要素の総和としてあり得る最大値を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

6
3 -1 -4 5 -9 2

出力例 1

8

S が空列である初期状態から、下記の通りに操作を行うことを考えます。

  • i = 1 について、S の末尾に A_1 = 3 を追加する。その結果、S = (3) となる。
  • i = 2 について、S の末尾に A_2 = -1 を追加する。その結果、S = (3, -1) となる。
  • i = 3 について、S の末尾の要素を削除する。その結果、S = (3) となる。
  • i = 4 について、S の末尾に A_4 = 5 を追加する。その結果、S = (3, 5) となる。
  • i = 5 について、S の末尾に A_5 = -9 を追加する。その結果、S = (3, 5, -9) となる。
  • i = 6 について、S の末尾の要素を削除する。その結果、S = (3, 5) となる。

このとき、すべての操作を終えた後の S の要素の総和は、3 + 5 = 8 であり、これがあり得る最大値です。

入力例 2

1
-1

出力例 2

-1

S が空のときは必ず、要素を追加する方の操作を選ばなければならないことに注意してください。

入力例 3

20
-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16

出力例 3

369

Score : 400 points

Problem Statement

You are given an integer sequence of length N: (A_1, A_2, \ldots, A_N). There is also a sequence S, which is initially empty.

For each i = 1, 2, \ldots, N in this order, you perform exactly one of the following two operations:

  • Append A_i as an element to the end of S.
  • Delete the last element of S. You cannot choose this operation if S is empty.

Print the maximum possible value of the sum of the elements of S after all operations.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq A_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

6
3 -1 -4 5 -9 2

Sample Output 1

8

Starting from the initial state where S is an empty sequence, consider the following operations:

  • For i = 1, append A_1 = 3 to the end of S. Now, S = (3).
  • For i = 2, append A_2 = -1 to the end of S. Now, S = (3, -1).
  • For i = 3, delete the last element of S. Now, S = (3).
  • For i = 4, append A_4 = 5 to the end of S. Now, S = (3, 5).
  • For i = 5, append A_5 = -9 to the end of S. Now, S = (3, 5, -9).
  • For i = 6, delete the last element of S. Now, S = (3, 5).

Here, the sum of the elements of S after all operations is 3 + 5 = 8, which is the maximum possible value.

Sample Input 2

1
-1

Sample Output 2

-1

Note that if S is empty, you must choose to append an element.

Sample Input 3

20
-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16

Sample Output 3

369