Let \(C_i\ (1 \leq i \leq M)\) be “the sequence obtained by performing the operation in the Problem Statement against \(B\) for each \(k=1,2,\dots,i−1,i+1,\dots,M\) in this order.” Also, let \(C_0\) be “the sequence obtained by performing the operation in the Problem Statement against \(B\) for each \(k=1,2,\dots,M\) in this order.” Since finding all \(C_i\) does not finish in the time limit, we try to find \(C_i\) fast enough using the property that the operation sequence that generates \(C_i\) and \(C_0\) are almost the same (only different in that whether we perform the operation on \(k=i\)).

First of all, \(C_i\) and \(C_0\) is in a very simple relation as follows:

• Let \(C'\) be the “sequence obtained by performing against \(B\) the operation described in the Problem statement for each \(k=1,2,\dots,i−1\)” (*). Then it holds for all \(j\ (1 \leq j \leq N)\) that:
  • if \((C_0)_j \neq x\) and \((C_0)_j \neq y\), then \((C_i)_j = (C_0)_j\);
  • if \((C_0)_j = x\), then \((C_i)_j = y\);
  • if \((C_0)_j = y\) then \((C_i)_j = x\).

For example, if \(C_0 = (1,3,x,2,y)\), then \(C_i = (1,3,y,2,x)\). This relation is understood by considering that “in \(C_i\), the positions of \(x\) and \(y\) is swapped by skipping the operation for \(k=i\), but it is not the case for all other elements.”

Therefore, denoting the value \(j\) such that \((C_0)_j = k\) by \(pos_k\), the value \(j\) such that \((C_i)_j = 1\) is found as follows:

Let us define \(C'\) just as we did in aforementioned (*). Then, - if \(C'_{A_i} \neq 1\) and \(C'_{A_i+1} \neq 1\), then \(j = pos_1\); - if \(C'_{A_i} = 1\), then \(j = pos_{C'_{A_i+1}}\); - if \(C'_{A_i+1} = 1\), then \(j = pos_{C'_{A_i}}\).

By finding \(C'\) for all \(C'\) and applying the rules above, we can solve the problem. The complexity is \(O(N+M)\).

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (int &i: a) {
        cin >> i;
    }
    
    // Find where do 1,2,...,N end up when we perform the operation for k = 1,2,...,M:
    vector<int> b(n + 1);
    iota(b.begin(), b.end(), 0);
    for (int i: a) {
        swap(b[i], b[i + 1]);
    }
    vector<int> pos(n + 1);
    for (int i = 1; i <= n; i++) {
        pos[b[i]] = i;
    }
    
    // find the answer
    iota(b.begin(), b.end(), 0);
    for (int i: a) {
        if (b[i] == 1) {
            cout << pos[b[i + 1]] << '\n';
        } else if (b[i + 1] == 1) {
            cout << pos[b[i]] << '\n';
        } else {
            cout << pos[1] << '\n';
        }
        swap(b[i], b[i + 1]);
    }
}