atcoder#ABC279E. [ABC279E] Cheating Amidakuji

[ABC279E] Cheating Amidakuji

Score : 500500 points

Problem Statement

You are given a sequence of length MM consisting of integers between 11 and N1N-1, inclusive: A=(A1,A2,,AM)A=(A_1,A_2,\dots,A_M). Answer the following question for i=1,2,,Mi=1, 2, \dots, M.

  • There is a sequence B=(B1,B2,,BN)B=(B_1,B_2,\dots,B_N). Initially, we have Bj=jB_j=j for each jj. Let us perform the following operation for k=1,2,,i1,i+1,,Mk=1, 2, \dots, i-1, i+1, \dots, M in this order (in other words, for integers kk between 11 and MM except ii in ascending order).- Swap the values of BAkB_{A_k} and BAk+1B_{A_k+1}.
  • Swap the values of BAkB_{A_k} and BAk+1B_{A_k+1}.
  • After all the operations, let SiS_i be the value of jj such that Bj=1B_j=1. Find SiS_i.

Constraints

  • 2N2×1052 \leq N \leq 2\times 10^5
  • 1M2×1051 \leq M \leq 2\times 10^5
  • 1AiN1 (1iM)1 \leq A_i \leq N-1\ (1\leq i \leq M)
  • All values in the input are integers.

Input

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

NN MM

A1A_1 A2A_2 \dots AMA_M

Output

Print MM lines. The ii-th line (1iM)(1\leq i \leq M) should contain the value SiS_i as an integer.

5 4
1 2 3 2
1
3
2
4

For i=2i = 2, the operations change BB as follows.

  • Initially, B=(1,2,3,4,5)B = (1,2,3,4,5).
  • Perform the operation for k=1k=1. That is, swap the values of B1B_1 and B2B_2, making B=(2,1,3,4,5)B = (2,1,3,4,5).
  • Perform the operation for k=3k=3. That is, swap the values of B3B_3 and B4B_4, making B=(2,1,4,3,5)B = (2,1,4,3,5).
  • Perform the operation for k=4k=4. That is, swap the values of B2B_2 and B3B_3, making B=(2,4,1,3,5)B = (2,4,1,3,5).

After all the operations, we have B3=1B_3=1, so S2=3S_2 = 3.

Similarly, we have the following.

  • For i=1i=1: performing the operation for k=2,3,4k=2,3,4 in this order makes B=(1,4,3,2,5)B=(1,4,3,2,5), so S1=1S_1=1.
  • For i=3i=3: performing the operation for k=1,2,4k=1,2,4 in this order makes B=(2,1,3,4,5)B=(2,1,3,4,5), so S3=2S_3=2.
  • For i=4i=4: performing the operation for k=1,2,3k=1,2,3 in this order makes B=(2,3,4,1,5)B=(2,3,4,1,5), so S4=4S_4=4.
3 3
2 2 2
1
1
1
10 10
1 1 1 9 4 4 2 1 3 3
2
2
2
3
3
3
1
3
4
4