\(0\)-indexed で考える． \(j \in M\) 番目を除いたものは， \([0,j) \) と \([j+1, M)\) に分解すると便利． 累積和などでも使われるが，今回も同様にできる．
あみだくじの上の方は，\(0\) の場所だけで十分． 下の方は，\([0, N)\) のすべての位置を持っておけば十分．
実装
下からシミュレーションする． 上からの様子は，前計算しておけば \(O(1)\) で答えられる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n >> m;
vll a(m); cinv(a);
rep(i,m){
a[i]--;
}
ll pos = 0; // position of 0
vll f(m+1); f[0] = pos;
rep(i,m) {
if(a[i] == pos) pos = a[i]+1;
else if(a[i]+1 == pos) pos = a[i]; // if ではだめ． それだと，pos が2回更新されることがあるから．
f[i+1] = pos; // i+1
}
vll p(n); rep(i,n) p[i] = i;
vll ans;
drep(i,m){ // rem : drep
ans.push_back(p[f[i]]);
swap(p[a[i]], p[a[i]+1]);
}
reverse(all(ans));
for(ll i: ans) cout << i+1 << endl;
return 0;
}
