AT_abc411_c [ABC411C] Black Intervals

左右一列に $ 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) $ 番目のマスは白く塗られている。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_Q $

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

### Sample Explanation 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 $ を改行区切りで出力します。 ### Sample Explanation 2 $ 2 $ 個目のクエリの後、すべてのマスは白く塗られているため、 $ 2 $ 行目には $ 0 $ を出力します。 ### Constraints - $ 1\leq N,Q\leq 5\times 10^5 $ - $ 1\leq A_i\leq N $ - 入力はすべて整数