Cho dãy nhị phân độ dài ~n~ và ~q~ truy vấn:

• ~i~: Gán ~a_i = 1 - a_i~.

Sau mỗi truy vấn, bạn cần tìm ~k~ lớn nhất sao cho tồn tại dãy số nguyên ~1 \leq i_1 < i_2 < \ldots < i_k \leq n~ thoả mãn ~a_{i_{j - 1}} + a_{i_{j + 1}} = 1~ với mọi ~1 < j < k~. In ra ~k~ tìm được.

Input

Dòng đầu gồm số nguyên dương ~n~ ~(1 \leq n \leq 10^5)~.

Dòng thứ hai gồm ~n~ ký tự ~0~ hoặc ~1~ thể hiện dãy nhị phân.

Dòng thứ ba chứa số nguyên dương ~q~ ~(1 \leq q \leq 10^5)~.

~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~i~ ~(1 \leq i \leq n~) thể hiện một truy vấn.

Output

In ra ~q~ dòng, mỗi dòng gồm một số nguyên dương là độ dài dãy con lớn nhất tìm được sau truy vấn tương ứng.

Scoring

Sample Input 1

7
1111111
4
1
2
5
7

Sample Output 1

3
4
5
6

Sample Input 2

1
1
2
1
1

Sample Output 2

1
1

Note:

Ở test ví dụ đầu tiên:

Sau truy vấn đầu tiên, dãy trở thành 0111111. Dãy con so le dài nhất tìm được là 011, có độ dài là ~3~.

Sau truy vấn thứ hai, dãy trở thành 0011111. Dãy con so le dài nhất tìm được là 0011, có độ dài là ~4~.

Sau truy vấn thứ ba, dãy trở thành 0011011. Dãy con so le dài nhất tìm được là 00110, có độ dài là ~5~.

Sau truy vấn thứ tư, dãy trở thành 0011010. Dãy con so le dài nhất tìm được là 001100, có độ dài là ~6~.