AT_arc066_c [ARC066E] Addition and Subtraction Hard

[problemUrl]: https://atcoder.jp/contests/arc066/tasks/arc066_c 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 $

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

### 制約 - $ 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 $ を出力します。