DP をします． \(dp[i][j]=(A_i=j\), \(A_{i-1}\neq j\) であるように \(A_1,\cdots,A_i\) を決める valiad な方法の数\()\) と定義します（便宜的に \(A_0\) は \(\infty\) などとしておきます）

また，\(dp2[i][j]=(A_i=j\) であるように \(A_1,\cdots,A_i\) を決める valiad な方法の数\()\) とします．

\(dp2[i][*]\) から \(dp[i+1][*]\) への遷移は一つの \(i\) に対して\(O(N)\) で計算でき，これで十分です．

次に \(dp[i][j]\) から \(dp2[k][j]\) への遷移を考えます． 各 \(k,j\) に対しに素直に計算すると \(1\) 回あたり \(O(N)\) かかってしまい間に合いません． しかし，必要な値は \(dp[l][j]+dp[l+1][j]+\cdots + dp[k][j]\) という形なので，累積和を用いれば \(O(1)\) に高速化できます．

結局，全体で \(O(N^2)\) で計算できます．

解答例