「\(B\) に対して \(k=1,2,\dots,i−1,i+1,\dots,M\) の順に問題文の操作を行うことで得られる数列」を \(C_i\ (1 \leq i \leq M)\) とおきます。また、「\(B\) に対して \(k=1,2,\dots,M\) の順に問題文の操作を行うことで得られる数列」を \(C_0\) とおきます。すべての \(C_i\) を愚直に求めるのは実行時間制限に間に合わないため、\(C_i\) と \(C_0\) の操作列がほとんど同じ (\(k=i\) について操作をするかしないかの違いしかない) ことを利用して、高速に \(C_i\) を求められないか考えます。

実際、\(C_i\) と \(C_0\) は、下記のように非常にシンプルな関係にあります。

• 「\(B\) に対して \(k=1,2,\dots,i−1\) の順に問題文の操作を行うことで得られる数列」を \(C'\) とする (＊)。また、\(x = C'_{A_i},y = C'_{A_i+1}\) とする。このとき、すべての \(j\ (1 \leq j \leq N)\) について以下が成り立つ。
  • \((C_0)_j \neq x\) かつ \((C_0)_j \neq y\) ならば、\((C_i)_j = (C_0)_j\)
  • \((C_0)_j = x\) ならば、\((C_i)_j = y\)
  • \((C_0)_j = y\) ならば、\((C_i)_j = x\)

例えば、\(C_0 = (1,3,x,2,y)\) のとき、\(C_i = (1,3,y,2,x)\) です。これらの関係は、「\(C_i\) においては、 \(k=i\) の操作を飛ばしたことでそれ以降での \(x\) と \(y\) の位置が \(C_0\) の時と逆転するが、\(x\) と \(y\) 以外には影響を及ぼさない」というように考えることで理解されます。

よって、\((C_0)_j = k\) を満たす \(j\) の値を \(pos_k\) とした時、\((C_i)_j = 1\) を満たす \(j\) の値は次のように求まります。

• 前述 (＊) と同じように \(C'\) を定義する。このとき、
  • \(C'_{A_i} \neq 1\) かつ \(C'_{A_i+1} \neq 1\) ならば、\(j = pos_1\)
  • \(C'_{A_i} = 1\) ならば、\(j = pos_{C'_{A_i+1}}\)
  • \(C'_{A_i+1} = 1\) ならば、\(j = pos_{C'_{A_i}}\)

\(i=1,2,\dots,M\) の順に \(C'\) を求め、上の規則を適用することによってこの問題を解くことができます。計算量は \(O(N+M)\) です。

実装例 (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;
    }
    
    // k = 1,2,...,M について操作を行った場合に、1,2,...,N がそれぞれどこに行くかを求める
    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;
    }
    
    // 答えを求める
    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]);
    }
}