AT_arc120_d [ARC120D] Bracket Score 2

[problemUrl]: https://atcoder.jp/contests/arc120/tasks/arc120_d **括弧の対応が取れている文字列**を、次のうちいずれかの条件を満たす文字列と定義します。 - 空文字列 - ある括弧の対応が取れている空でない文字列 $ s,\ t $ が存在し、$ s,\ t $ をこの順に連結した文字列 - ある括弧の対応が取れている文字列 $ s $ が存在し、 `(`, $ s $, `)` をこの順に連結した文字列 また、括弧の対応が取れている文字列 $ s $ の $ i $ 文字目と $ j $ 文字目が**対応している**とは、以下の条件を全て満たすこととします。 - $ 1\ \le\ i\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ A_3 $ $ \dots $ $ A_{2N} $

長さ $ 2N $ の括弧の対応が取れている文字列のうち、スコアが最大となるような文字列を $ 1 $ つ出力せよ。 正しい答えが複数存在する場合、どれを出力しても正解と判定される。

### 制約 - $ 1\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ A_i\ \le\ 10^9 $ - 入力に含まれる値は全て整数 ### Sample Explanation 1 長さ $ 4 $ の括弧の対応が取れている文字列は `(())` と `()()` の $ 2 $ 種類あり、それぞれのスコアは以下の通りです。 - `(())` : $ |1\ -\ 4|\ +\ |2\ -\ 3|\ =\ 4 $ - `()()` : $ |1\ -\ 2|\ +\ |3\ -\ 4|\ =\ 2 $ よって、`(())` のみが正しい答えとなります。 ### Sample Explanation 2 `(())` と `()()` のスコアは以下の通りです。 - `(())` : $ |2\ -\ 3|\ +\ |3\ -\ 2|\ =\ 2 $ - `()()` : $ |2\ -\ 3|\ +\ |2\ -\ 3|\ =\ 2 $ よって、この場合どちらを出力しても正解となります。