E - カッコ列

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 1100

問題文

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

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

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

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

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

制約

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

入力

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

N Q
S
k_1
:
k_Q

出力

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


入力例 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