以下、\(A_k\) を \(A_{k+1}\) で置き換える操作を操作 \(k\) と呼ぶこととします。

\(A=(1,2,\dots,N)\) の場合を考えます。\((1,2,\dots,N)\) は操作 \(0\) 回で作ることが出来ます。以降、操作回数は \(1\) 回以上とします。

\(1\) 回操作をした場合、\(A\) に出てくる整数の種類は \(N-1\) 種類となり、これは増加することがありません。よって、作ることのできる \(A\) に出てくる整数の種類は \(N-1\) 種類以下です。

また、操作によって「ある整数 \(i\) が存在し \(A_i \le A_{i+1} \le ... \le A_N \le A_1 \le ... \le A_{i-2} \le A_{i-1}\) を満たす。」という性質は失われることがないため、これも必要条件です。

そして、これらが必要十分条件となっています。

まず、以下の性質を証明します。

• \(1\) 回以上操作を行っているとき、\(A\) を左 shift させることが出来る。

よって、\(A\) を \(X_1\) が \(Y_1\) 個、\(X_2\) が \(Y_2\) 個、\(\dots\) \(X_k\) を \(Y_k\) 個がこの順で並んでいるとみなせます。\((X_1 < X_2 < \dots < X_k,\sum_{i=1}^{k} Y_i = N)\) 例えば、\(A=(1,1,3,4)\) のときは \(X=(1,3,4),Y=(2,1,1)\) となります。\(A=(1,3,3,6,1,1)\) のときは\(X=(1,3,6),Y=(3,2,1)\) となります。

ここで、\(X_i\) と \(X_{i+1}\) の境目で操作をすると \(Y_i\) を \(1\) 減らし、\(Y_{i+1}\) を \(1\) 増やすことが出来るため、全ての \(Y\) を作ることが出来ます。よって先ほどの性質と合わせ、必要十分条件となっていることが証明できました。

\(A\) が一般の時を解きます。まず、\(A=B\) の場合は Yes です。そうでなく、圧縮後の \(B\) の長さが \(N\) ならば No です。

上 \(2\) 個に当てはまらない場合、\(B\) を rotate して作ることのできる \(N\) 種類の数列 \(C\) に対して以下を判定し、いずれかが Yes ならば Yes となります。

• ある単調増加整数列 \(x_1 \le x_2 \le \dots \le x_{N-1} \le x_N\) が存在し、\(C_i = A_{x_i}\) が成り立つ。

これは、貪欲法で \(\mathrm{O}(N)\) で判定できるため、全ての \(C\) に愚直に判定しても \(\mathrm{O}(N^2)\) でこの問題を解くことが出来ます。