問題文

長さ m の文字列について、これが対応付いているとは、文字列が( と )からなり、(と)の数が等しく、どの i(≦m) についても、先頭 i 文字目までで(の数が)の数以上であるということを指します。例えば、(())や()(()())は対応付いた文字列で、)(や())、abcなどは対応付いた文字列ではありません。

対応付いた文字列について、そのスコアを)の添字の総和から、(の添字の総和を引いたものとして定義します。添字とは、その文字が左から何文字目に位置するかを表す整数です。例えば、(())についてスコアは 4 であり、()(()()) についてスコアは 8 です。

文字列の部分列とは、文字列からいくつかの文字を削除したのち、残った文字列の順番を変えずにつなげたものを指します。例えば、())について、空文字列、 ())や()は部分列ですが、)(は部分列ではありません。

はじめ、あなたは長さ N の文字列 S を持っています。以下のクエリーを Q 回処理するプログラムを書いてください。

• i番目のクエリーは、整数 k_i が与えられる。
• S の k_i 番目の文字を逆にする。すなわち、 ( なら ) にし、) なら ( にする。
• 編集後、S から取れる対応付いた部分列のスコアのうち、最大値を答えよ。

制約

• 1≦N, Q≦10^5
• S は ( と ) のみからなる
• 1≦k_i≦N

入力例 1

5 4
()(()
5
2
5
4

出力例 1

1
0
1
4

クエリーにより、文字列は

• ()(((
• (((((
• (((()
• ((())

と変化します。各文字列で取れる最大のスコアの部分列は、それぞれ

• ()
• (空文字列)
• ()
• (())

です。

入力例 2

5 3
(()))
2
1
5

出力例 2

1
0
0

入力例 3

6 6
())()(
3
4
1
5
6
2

出力例 3

2
4
1
1
2
4