Let’s consider the structure of \(A\) such that all intervals are good intervals.

First, focusing on interval \([i,i+1]\), for any \(i\), we need \(A_i=i+1\) or \(A_{i+1}=i\). (★)

In the following, we correspond \(A\) to a string \(S\) of length \(N\), where \(S_i\) is R when \(A_i=i+1\), L when \(A_i=i-1\), and X otherwise.

When \(S_i\) is R, focusing on interval \([i-1,i]\), \(S_{i-1}\) must also be R. The same applies to L, so combined with (★), we find that \(S\) has the following structure:

• R…RXL…L (where there are zero or more Rs and Ls, and zero or one X)

By exhaustively searching whether X is included and, if so, the position of \(X\), or if not, the position of the RL boundary, and determining whether the input \(A\) can satisfy the conditions, we can solve this problem in \(O(N)\).