|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|5 초||256 MB||58||33||30||60.000%|
A string consisting only of parentheses ‘(’ and ‘)’ is called balanced if it is one of the following.
Note that the condition is stronger than merely the numbers of ‘(’ and ‘)’ are equal. For instance, “())(()” is not balanced.
Your task is to keep a string in a balanced state, under a severe condition in which a cosmic ray may flip the direction of parentheses.
You are initially given a balanced string. Each time the direction of a single parenthesis is flipped, your program is notified the position of the changed character in the string. Then, calculate and output the leftmost position that, if the parenthesis there is flipped, the whole string gets back to the balanced state. After the string is balanced by changing the parenthesis indicated by your program, next cosmic ray flips another parenthesis, and the steps are repeated several times.
The input consists of a single test case formatted as follows.
N Q s q1 . . . qQ
The first line consists of two integers N and Q (2 ≤ N ≤ 300000, 1 ≤ Q ≤ 150000). The second line is a string s of balanced parentheses with length N. Each of the following Q lines is an integer qi (1 ≤ qi ≤ N) that indicates that the direction of the qi-th parenthesis is flipped.
For each event qi, output the position of the leftmost parenthesis you need to flip in order to get back to the balanced state.
Note that each input flipping event qi is applied to the string after the previous flip qi−1 and its fix.
6 3 ((())) 4 3 1
2 2 1
20 9 ()((((()))))()()()() 15 20 13 5 3 10 3 17 18
2 20 8 5 3 2 2 3 18
In the first sample, the initial state is “((()))”. The 4th parenthesis is flipped and the string becomes “(((())”. Then, to keep the balance you should flip the 2nd parenthesis and get “()(())”. The next flip of the 3rd parenthesis is applied to the last state and yields “())())”. To rebalance it, you have to change the 2nd parenthesis again yielding “(()())”.