全ての区間が良い区間となるような \(A\) の構造を考えます。

まず、区間 \([i,i+1]\) に着目すると、任意の \(i\) に対して\(A_i=i+1\) または \(A_{i+1}=i\) が必要です。（★）

以下では、\(A\) と長さ \(N\) の文字列 \(S\) を対応させることとし、\(A_i=i+1\) のとき \(S_i\) を R、\(A_i=i-1\) のとき \(S_i\) を L、それ以外のとき \(S_i\) を X とします。

\(S_i\) が R のとき、区間 \([i-1,i]\) に着目すると \(S_{i-1}\) も R である必要があります。また、L についても同様なので、（★）も合わせると結局 \(S\) は以下の構造をしていることが分かります。

• R…RXL…L(ここで R,L は \(0\) 文字以上、X は \(0\) 文字または \(1\) 文字）

X が含まれるか、含まれる場合は \(X\) の位置を、含まれない場合は RL の境界の位置を全探索し、入力の \(A\) が条件を満たせるかを判定することで、この問題を \(O(N)\) で解けます。