Problem Description

For a string of length $ m $, it is said to be balanced if the string consists of only ( and ), has an equal number of ( and ), and for any $ i (≤ m) $, the number of ( up to the $ i $-th character is at least the number of ). For example, (()) and ()(()()) are balanced strings, while )(, ()), and abc are not.

For a balanced string, its score is defined as the sum of the indices of ) minus the sum of the indices of (. The index refers to the position of the character from the left as an integer. For example, the score for (()) is $ 4 $, and for ()(()()) it is $ 8 $.

A subsequence of a string is a string obtained by deleting some characters from the original string without changing the order of the remaining characters. For example, for ()), the subsequences include the empty string, ()), and (), but )( is not a subsequence.

Initially, you have a string $ S $ of length $ N $. Write a program to process $ Q $ queries as follows:

• The $ i $-th query provides an integer $ k_i $.
• Reverse the $ k_i $-th character of $ S $. That is, change ( to ) or ) to (.
• After editing, answer the maximum score of a balanced subsequence that can be obtained from $ S $.

Input Format

The input is provided from standard input in the following format:

$ N $ $ Q $ $ S $ $ k_1 $ $ : $ $ k_Q $

Output Format

Output the answers to the queries in order.

Sample Input and Output

Sample Input #1

5 4
()(()
5
2
5
4

Sample Output #1

1
0
1
4

Sample Input #2

5 3
(()))
2
1
5

Sample Output #2

1
0
0

Sample Input #3

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

Sample Output #3

2
4
1
1
2
4

Notes/Hints

Constraints

• $ 1 ≦ N, Q ≦ 10^5 $
• $ S $ consists only of ( and )
• $ 1 ≦ k_i ≦ N $

Sample Explanation 1

The string changes due to the queries as follows: - ()((( - ((((( - (((() - ((()). The maximum score subsequences for each string are: - () - (empty string) - () - (()).

见题面 Input 部分

见题面 Output 部分