\(i\) 番目の操作で \(A_i=A_{i+1}\) の場合入れ替えを禁止することにすると，操作列と最終的な数列を一対一対応させることができる．

上の条件を課した上で \(i-1\) 番目の操作まで行ったとき，\(i\) 番目の要素が \(k\) であるような操作列の個数を \(\mathrm{dp}[k]\) とすると，\(\mathrm{dp}[A_{i+1}]\) に \(k\neq A_{i+1}\) であるような全ての \(\mathrm{dp}[k]\) を足しこむ操作が実現できれば良い．（この遷移は \(i\) 番目の操作で入れ替えないことに対応している．）

この操作は \(\mathrm{dp}\) の総和を管理することで \(\mathrm{O}(1)\) で可能なので \(\mathrm{O}(N)\) でこの問題を解ける．