The key point of this problem is not to count duplicate operations that produce the same result.

Operations \((L,R)\) and \((L-1,R)\) are the same operation when \(A_L=A_{L-1}\). Also, operations \((L,R)\) and \((L,R-1)\) are the same operation when \(A_L=A_R\).

Furthermore, it can be proved that operation results for \((L,R)\) satisfying \(A_L\neq A_{L-1},A_L\neq A_R\) are all distinct. This follows from establishing a one-to-one correspondence between the range changed by the operation and operation ranges that are maximal with respect to the left and minimal with respect to the right.

Therefore, we need to count integer pairs \((L,R)\) satisfying \(A_L\neq A_{L-1},A_L\neq A_R\). A naive approach takes \(O(N^2)\), but by iterating \(L\) in descending order and maintaining a table where \(\mathrm{cnt}[x]\) is defined as the number of \(i\) satisfying \(i\geq L\) and \(A_i=x\), we can speed this up to \(O(N)\).