AT_arc194_a [ARC194A] Operations on a Stack

長さ $ N $ の整数列 $ (A_1, A_2, \ldots, A_N) $ が与えられます。 また、列 $ S $ があり、 $ S $ ははじめは空列です。 $ i = 1, 2, \ldots, N $ の順に、それぞれの $ i $ について、下記の $ 2 $ つの操作のうちちょうど $ 1 $ つを行います。 - $ S $ の末尾に $ A_i $ を要素として追加する。 - $ S $ の末尾の要素を削除する。ただし $ S $ が空のときは、この操作を行うことを選択できない。 すべての操作を終えた後の、 $ S $ の要素の総和としてあり得る最大値を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

答えを出力せよ。

### Sample Explanation 1 $ 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 $ であり、これがあり得る最大値です。 ### Sample Explanation 2 $ S $ が空のときは必ず、要素を追加する方の操作を選ばなければならないことに注意してください。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ -10^9 \leq A_i \leq 10^9 $ - 入力はすべて整数