题目描述

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

输入格式

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

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

输出格式

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

题目大意

给你一个只包含'+'、'-'、正整数的式子，你需要在式子中添加一些括号，使运算结果最大，输出最大的结果。

3
5 - 1 - 3

7

5
1 - 2 + 3 - 4 + 5

5

5
1 - 20 - 13 + 14 - 5

13

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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