E - Addition and Subtraction Hard

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 900

問題文

joisinoお姉ちゃんは、N 項から成る式、A_1 op_1 A_2 ... op_{N-1} A_N を持っています。 ここで、A_i は整数で、op_i は、+ または - の記号です。 joisinoお姉ちゃんは大きい数が好きなので、括弧を好きな数だけ( 0 個でもよい)挿入することで、計算の順番を変え、式の値を最大化したいです。 開き括弧は数の直前、閉じ括弧は数の直後にのみ、挿入することが許されます。 同じ場所に挿入する括弧の個数に制限はありません。 あなたの仕事は、式に括弧をいくつか挿入した際に、式の値としてありうるものの最大値を求めるプログラムを作ることです。

制約

  • 1≦N≦10^5
  • 1≦A_i≦10^9
  • op_i は、+ または - の記号である。

入力

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

N
A_1 op_1 A_2 ... op_{N-1} A_N

出力

括弧をいくつか挿入してできる式の値としてありうるものの最大値を出力せよ。


入力例 1

3
5 - 1 - 3

出力例 1

7

5 - (1 - 3) = 7 となり、これが最大なので、7 を出力します。


入力例 2

5
1 - 2 + 3 - 4 + 5

出力例 2

5

1 - (2 + 3 - 4) + 5 = 5 となり、これが最大なので、5 を出力します。


入力例 3

5
1 - 20 - 13 + 14 - 5

出力例 3

13

1 - (20 - (13 + 14) - 5) = 13 となり、これが最大なので、13 を出力します。

Score : 900 points

Problem Statement

Joisino has a formula consisting of N terms: A_1 op_1 A_2 ... op_{N-1} A_N. Here, A_i is an integer, and op_i is an binary operator either + or -. Because Joisino loves large numbers, she wants to maximize the evaluated value of the formula by inserting an arbitrary number of pairs of parentheses (possibly zero) into the formula. Opening parentheses can only be inserted immediately before an integer, and closing parentheses can only be inserted immediately after an integer. It is allowed to insert any number of parentheses at a position. Your task is to write a program to find the maximum possible evaluated value of the formula after inserting an arbitrary number of pairs of parentheses.

Constraints

  • 1≦N≦10^5
  • 1≦A_i≦10^9
  • op_i is either + or -.

Input

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

N
A_1 op_1 A_2 ... op_{N-1} A_N

Output

Print the maximum possible evaluated value of the formula after inserting an arbitrary number of pairs of parentheses.


Sample Input 1

3
5 - 1 - 3

Sample Output 1

7

The maximum possible value is: 5 - (1 - 3) = 7.


Sample Input 2

5
1 - 2 + 3 - 4 + 5

Sample Output 2

5

The maximum possible value is: 1 - (2 + 3 - 4) + 5 = 5.


Sample Input 3

5
1 - 20 - 13 + 14 - 5

Sample Output 3

13

The maximum possible value is: 1 - (20 - (13 + 14) - 5) = 13.