{"problem":{"name":"Cheating Amidakuji","description":{"content":"You are given a sequence of length $M$ consisting of integers between $1$ and $N-1$, inclusive: $A=(A_1,A_2,\\dots,A_M)$. Answer the following question for $i=1, 2, \\dots, M$. *   There is a sequence ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc279_e"},"statements":[{"statement_type":"Markdown","content":"You are given a sequence of length $M$ consisting of integers between $1$ and $N-1$, inclusive: $A=(A_1,A_2,\\dots,A_M)$. Answer the following question for $i=1, 2, \\dots, M$.\n\n*   There is a sequence $B=(B_1,B_2,\\dots,B_N)$. Initially, we have $B_j=j$ for each $j$. Let us perform the following operation for $k=1, 2, \\dots, i-1, i+1, \\dots, M$ in this order (in other words, for integers $k$ between $1$ and $M$ except $i$ in ascending order).\n    *   Swap the values of $B_{A_k}$ and $B_{A_k+1}$.\n*   After all the operations, let $S_i$ be the value of $j$ such that $B_j=1$. Find $S_i$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2\\times 10^5$\n*   $1 \\leq M \\leq 2\\times 10^5$\n*   $1 \\leq A_i \\leq N-1\\ (1\\leq i \\leq M)$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\dots$ $A_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc279_e","tags":[],"sample_group":[["5 4\n1 2 3 2","1\n3\n2\n4\n\nFor $i = 2$, the operations change $B$ as follows.\n\n*   Initially, $B = (1,2,3,4,5)$.\n*   Perform the operation for $k=1$. That is, swap the values of $B_1$ and $B_2$, making $B = (2,1,3,4,5)$.\n*   Perform the operation for $k=3$. That is, swap the values of $B_3$ and $B_4$, making $B = (2,1,4,3,5)$.\n*   Perform the operation for $k=4$. That is, swap the values of $B_2$ and $B_3$, making $B = (2,4,1,3,5)$.\n\nAfter all the operations, we have $B_3=1$, so $S_2 = 3$.\nSimilarly, we have the following.\n\n*   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$.\n*   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$.\n*   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$."],["3 3\n2 2 2","1\n1\n1"],["10 10\n1 1 1 9 4 4 2 1 3 3","2\n2\n2\n3\n3\n3\n1\n3\n4\n4"]],"created_at":"2026-03-03 11:01:13"}}