D - Insert XOR 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

0 と 1 からなる長さ N の整数列 A=(A_1,A_2,\dots,A_N) があります。 Q 個のクエリが与えられます。 q 番目のクエリは以下のようなものです。

  • 1 以上 N 以下の整数 i_q が与えられる。A_{i_q} が 0 なら 1 に、1 なら 0 に変更する。

各クエリを処理するたびに、以下の問題の答えを求めてください。

0 と 1 からなる数列 B=(B_1,B_2,\dots,B_{|B|}) のうち以下の条件を満たすものを考えます。

  • B に対して以下の操作を好きな回数行って、数列 A と一致させることができる。
    • 1 以上 |B|-1 以下の整数 i を選ぶ。
    • B_i と B_{i+1} の間に B_i\oplus B_{i+1} を挿入する。
条件を満たす B は必ず存在することが証明できます。 |B| として考えられる値の最小値を求めてください。

制約

  • 3 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 1
  • 1 \leq Q \leq 5 \times 10^5
  • 1 \leq i_q \leq N
  • 入力される値は全て整数

入力

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

N
A_1 A_2 \dots A_N
Q
i_1
i_2
\vdots
i_Q

出力

答えを合計 Q 行で出力せよ。 q 行目には、q 番目のクエリを処理した後の問題の答えを出力せよ。

入力例 1

3
0 0 0
2
1
2

出力例 1

3
2

A=(1,0,0) のとき、|B| は B=(1,0,0) で最小となります。 A=(1,1,0) のとき、|B| は B=(1,0) で最小となります。

入力例 2

8
0 1 0 0 1 1 1 0
3
1
4
1

出力例 2

5
2
3

Score : 800 points

Problem Statement

There is an integer sequence A=(A_1,A_2,\dots,A_N) of length N consisting of 0 and 1. You are given Q queries. The q-th query is as follows:

  • An integer i_q between 1 and N is given. Change A_{i_q} to 1 if it is 0, and to 0 if it is 1.

After processing each query, find the answer to the following problem:

Consider sequences B=(B_1,B_2,\dots,B_{|B|}) consisting of 0 and 1 that satisfy the following condition:

  • By performing the following operation any number of times on B, it can be made to match sequence A:
    • Choose an integer i between 1 and |B|-1, inclusive.
    • Insert B_i\oplus B_{i+1} between B_i and B_{i+1}.
It can be proved that there always exists a B that satisfies the condition. Find the minimum possible value of |B|.

Constraints

  • 3 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 1
  • 1 \leq Q \leq 5 \times 10^5
  • 1 \leq i_q \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
Q
i_1
i_2
\vdots
i_Q

Output

Output the answers in a total of Q lines. The q-th line should contain the answer to the problem after processing the q-th query.

Sample Input 1

3
0 0 0
2
1
2

Sample Output 1

3
2

When A=(1,0,0), |B| is minimized by B=(1,0,0). When A=(1,1,0), |B| is minimized by B=(1,0).

Sample Input 2

8
0 1 0 0 1 1 1 0
3
1
4
1

Sample Output 2

5
2
3