We perform dynamic programming. Let \(dp[i][j]\) be the number of valid ways to determine \(A_1,\cdots,A_i\) such that \(A_i=j\) and \(A_{i-1}\neq j\) (for convenience, let’s assume \(A_0\) is \(\infty\) or something similar).

Also, let \(dp2[i][j]\) be the number of valid ways to determine \(A_1,\cdots,A_i\) such that \(A_i=j\).

The transition from \(dp2[i][*]\) to \(dp[i+1][*]\) can be calculated in \(O(N)\) for a single \(i\), and this is sufficient.

Next, we consider the transition from \(dp[i][j]\) to \(dp2[k][j]\). If we calculate this naively, it takes \(O(N)\) time for each \(k,j\), which is not fast enough. However, the required value is in the form of \(dp[l][j]+dp[l+1][j]+\cdots + dp[k][j]\), so using cumulative sums can speed it up to \(O(1)\).

Eventually, the entire process can be calculated in \(O(N^2)\) time.

Sample Solution