AT_soundhound2018_e カッコ列

[problemUrl]: https://atcoder.jp/contests/soundhound2018/tasks/soundhound2018_e 長さ $ m $ の文字列について、これが対応付いているとは、文字列が`(` と `)`からなり、`(`と`)`の数が等しく、どの $ i(≦m) $ についても、先頭 $ i $ 文字目までで`(`の数が`)`の数以上であるということを指します。例えば、`(())`や`()(()())`は対応付いた文字列で、`)(`や`())`、`abc`などは対応付いた文字列ではありません。 対応付いた文字列について、そのスコアを`)`の添字の総和から、`(`の添字の総和を引いたものとして定義します。添字とは、その文字が左から何文字目に位置するかを表す整数です。例えば、`(())`についてスコアは $ 4 $ であり、`()(()())` についてスコアは $ 8 $ です。 文字列の部分列とは、文字列からいくつかの文字を削除したのち、残った文字列の順番を変えずにつなげたものを指します。例えば、`())`について、空文字列、 `())`や`()`は部分列ですが、`)(`は部分列ではありません。 はじめ、あなたは長さ $ N $ の文字列 $ S $ を持っています。以下のクエリーを $ Q $ 回処理するプログラムを書いてください。 - $ i $番目のクエリーは、整数 $ k_i $ が与えられる。 - $ S $ の $ k_i $ 番目の文字を逆にする。すなわち、 `(` なら `)` にし、`)` なら `(` にする。 - 編集後、$ S $ から取れる対応付いた部分列のスコアのうち、最大値を答えよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ S $ $ k_1 $ $ : $ $ k_Q $

クエリーに対する答えを順に出力せよ。

### 制約 - $ 1≦N,\ Q≦10^5 $ - $ S $ は `(` と `)` のみからなる - $ 1≦k_i≦N $ ### Sample Explanation 1 クエリーにより、文字列は - `()(((` - `(((((` - `(((()` - `((())` と変化します。各文字列で取れる最大のスコアの部分列は、それぞれ - `()` - (空文字列) - `()` - `(())` です。