操作結果が等しい操作を重複して数えないことがこの問題のキーポイントです。

操作 \((L,R)\) と \((L-1,R)\) は、\(A_L=A_{L-1}\) のとき同じ操作です。 また、操作 \((L,R)\) と \((L,R-1)\) は \(A_L=A_R\) のとき同じ操作です。

また、\(A_L\neq A_{L-1},A_L\neq A_R\) を満たすような \((L,R)\) に対する操作結果は相異なることが証明できます。これは、操作によって変化する範囲と、左に対して極大、右に対して極小な操作範囲を一対一対応させていることから従います。

よって \(A_L\neq A_{L-1},A_L\neq A_R\) を満たす整数組 \((L,R)\) を数えられれば良いです。愚直に行うと \(O(N^2)\) ですが、\(L\) を降順に回し、\(\mathrm{cnt}[x]\) を \(i\geq L\) かつ \(A_i=x\) を満たす \(i\) の個数と定義したテーブルを管理することで \(O(N)\) に高速化できます。