8269: ABC279 —— E - Cheating Amidakuji
[Creator : ]
Description
You are given a sequence of length M consisting of integers between 1 and N−1, inclusive: $A=(A_1,A_2,…,A_M)$. Answer the following question for i=1,2,…,M.
-
There is a sequence $B=(B_1,B_2,…,B_N)$. Initially, we have $B_j=j$ for each j. Let us perform the following operation for k=1,2,…,i−1,i+1,…,M in this order (in other words, for integers k between 1 and M except i in ascending order).
- Swap the values of $B_{A_k}$ and $B_{A_{k+1}}$.
- After all the operations, let $S_i$ be the value of j such that $B_j=1$. Find $S_i$.
Input
The input is given from Standard Input in the following format:
$N\ M$
$A_1\ A_2\ …\ A_M$
$N\ M$
$A_1\ A_2\ …\ A_M$
Output
Print M lines. The i-th line (1≤i≤M) should contain the value $S_i$ as an integer.
Constraints
$2≤N≤2×10^5$
$1≤M≤2×10^5$
$1≤A_i≤N−1\ (1≤i≤M)$
All values in the input are integers.
$1≤M≤2×10^5$
$1≤A_i≤N−1\ (1≤i≤M)$
All values in the input are integers.
Sample 1 Input
5 4
1 2 3 2
Sample 1 Output
1
3
2
4
For i=2, the operations change B as follows.
- Initially, B=(1,2,3,4,5).
- Perform the operation for k=1. That is, swap the values of $B_1$ and $B_2$, making B=(2,1,3,4,5).
- Perform the operation for k=3. That is, swap the values of $B_3$ and $B_4$, making B=(2,1,4,3,5).
- Perform the operation for k=4. That is, swap the values of $B_2$ and $B_3$, making B=(2,4,1,3,5).
After all the operations, we have $B_3=1$, so $S_2=3$.
Similarly, we have the following.
- For i=1: performing the operation for k=2,3,4 in this order makes B=(1,4,3,2,5), so $S_1=1$.
- For i=3: performing the operation for k=1,2,4 in this order makes B=(2,1,3,4,5), so $S_3=2$.
- For i=4: performing the operation for k=1,2,3 in this order makes B=(2,3,4,1,5), so $S_4=4$.
Sample 2 Input
3 3
2 2 2
Sample 2 Output
1
1
1
Sample 3 Input
10 10
1 1 1 9 4 4 2 1 3 3
Sample 3 Output
2
2
2
3
3
3
1
3
4
4