Problem Description

哪个出题人会不喜欢一道人畜无害的括号题呢？

给定一个长度为 $n$ 的括号串 $s$，$s$ 仅由字符 `(` 和 `)` 组成。

定义「合法括号序列」为仅由 `(` 和 `)` 构成的字符串，且满足：

$\quad$· 空串 $\varepsilon$ 是合法括号序列。

$\quad$· 如果 $A$ 是合法括号序列，那么 `(A)` 也是合法括号序列。

$\quad$· 如果 $A, B$ 都是合法括号序列，那么 $AB$ 也是合法括号序列。

若一个前缀本身是合法括号序列，则称其为「正则前缀」。

现有 $q$ 次操作，每次给定下标 $p_i$：

$\quad$· 翻转 $s$ 的第 $p_i$ 个字符，即`(` 变为 `)`，`)` 变为 `(`。

每次操作后，你需要输出当前 $s$ 中的非空正则前缀数量，修改是持久的。

Input Format

第一行两个整数 $n, q$（$1 \le n, q \le 10^5$）。

第二行一个长度为 $n$ 的字符串 $s$。保证该字符串中的字符只有$'('$和$')'$。

接下来 $q$ 行，每行一个整数 $p_i$（$1 \le p_i \le n$）。

Output Format

共 $q$ 行，第 $i$ 行输出第 $i$ 次操作后正则前缀的非空数量。

2 2
)(
1
2

0
1

4 3
()((
2
2
4

0
1
2