C - Black Intervals 解説 /

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

配点 : 350 点

問題文

左右一列に N 個のマスが並んでいます。 最初、すべてのマスは白く塗られています。

Q 個のクエリを順に処理してください。i 個目のクエリでは 1 以上 N 以下の整数 A_i が与えられ、次の操作を行います。

左から A_i 番目のマスの色を反転させる。 具体的には、左から A_i 番目のマスが、白く塗られていたならば黒く塗り、黒く塗られていたならば白く塗る。
その後、黒く塗られたマスが連続している区間の個数を求める。

ここで、黒く塗られたマスが連続している区間とは次をすべてみたす整数の組 (l,r) (1\leq l\leq r\leq N) を指す。

  • 左から l, l+1, \ldots, r 番目のマスはすべて黒く塗られている。
  • l=1 であるか、または左から (l-1) 番目のマスは白く塗られている。
  • r=N であるか、または左から (r+1) 番目のマスは白く塗られている。

制約

  • 1\leq N,Q\leq 5\times 10^5
  • 1\leq A_i\leq N
  • 入力はすべて整数

入力

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

N Q
A_1 A_2 \ldots A_Q

出力

Q 行出力せよ。i 行目 (1\leq i\leq Q) には i 個目のクエリの答えを出力せよ。

入力例 1

5 7
2 3 3 5 1 5 2

出力例 1

1
1
1
2
2
1
1

以下では、左から i 番目のマスを マス i と表します。
各クエリの後は次のような状態になっています。

  • 1 個目のクエリの後、マス 2 のみが黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(2,2) の 1 つです。
  • 2 個目のクエリの後、マス 2,3 が黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(2,3) の 1 つです。
  • 3 個目のクエリの後、マス 2 のみが黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(2,2) の 1 つです。
  • 4 個目のクエリの後、マス 2,5 が黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(2,2), (5,5) の 2 つです。
  • 5 個目のクエリの後、マス 1,2,5 が黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(1,2), (5,5) の 2 つです。
  • 6 個目のクエリの後、マス 1,2 のみが黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(1,2) の 1 つです。
  • 7 個目のクエリの後、マス 1 のみが黒く塗られています。黒く塗られたマスが連続している区間は (l,r)=(1,1) の 1 つです。

よって、1,1,1,2,2,1,1 を改行区切りで出力します。

入力例 2

1 2
1 1

出力例 2

1
0

2 個目のクエリの後、すべてのマスは白く塗られているため、2 行目には 0 を出力します。

入力例 3

3 3
1 3 2

出力例 3

1
2
1

Score : 350 points

Problem Statement

There are N squares arranged in a row from left to right. Initially, all squares are painted white.

Process Q queries in order. The i-th query gives an integer A_i between 1 and N, inclusive, and performs the following operation:

Flip the color of the A_i-th square from the left. Specifically, if the A_i-th square from the left is painted white, paint it black; if it is painted black, paint it white.
Then, find the number of intervals of consecutively painted black squares.

Here, an interval of consecutively painted black squares is a pair of integers (l,r) (1\leq l\leq r\leq N) that satisfy all of the following:

  • The l-th, (l+1)-th, \ldots, r-th squares from the left are all painted black.
  • Either l=1, or the (l-1)-th square from the left is painted white.
  • Either r=N, or the (r+1)-th square from the left is painted white.

Constraints

  • 1\leq N,Q\leq 5\times 10^5
  • 1\leq A_i\leq N
  • All input values are integers.

Input

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

N Q
A_1 A_2 \ldots A_Q

Output

Output Q lines. On the i-th line (1\leq i\leq Q), output the answer to the i-th query.

Sample Input 1

5 7
2 3 3 5 1 5 2

Sample Output 1

1
1
1
2
2
1
1

Below, the i-th square from the left is referred to as square i.
After each query, the state is as follows:

  • After the 1st query, only square 2 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,2).
  • After the 2nd query, squares 2,3 are painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,3).
  • After the 3rd query, only square 2 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,2).
  • After the 4th query, squares 2,5 are painted black. There are 2 intervals of consecutively painted black squares: (l,r)=(2,2), (5,5).
  • After the 5th query, squares 1,2,5 are painted black. There are 2 intervals of consecutively painted black squares: (l,r)=(1,2), (5,5).
  • After the 6th query, only squares 1,2 are painted black. There is 1 interval of consecutively painted black squares: (l,r)=(1,2).
  • After the 7th query, only square 1 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(1,1).

Thus, output 1,1,1,2,2,1,1 separated by newlines.

Sample Input 2

1 2
1 1

Sample Output 2

1
0

After the 2nd query, all squares are painted white, so output 0 on the 2nd line.

Sample Input 3

3 3
1 3 2

Sample Output 3

1
2
1