The answer is the number of subarrays containing \(1\) \(+\) the number of subarrays containing \(2\) \(+\ldots+\) the number of subarrays containing \(N\).

We will explain how to count subarrays containing \(i\) in \(\mathrm{O}(C_i)\) time (where \(C_i\) is the number of occurrences of \(i\) in \(A\)). Once this is possible, the problem can be solved in a total of \(\mathrm{O}(N)\) time.

A common technique of combinatorics is to consider complementary events. Let’s follow the custom and count the number of subarrays not containing \(i\), subtracting the sum from the all.

For simplicity, let us insert \(i\) to the both ends of \(A\) (which does not change the count).

Then, the indices \(x\) with \(A_x = i\) arranged in ascending order are represented as \(x=(x_0=0,x_1,\ldots,x_{C_i+1} = N+1)\). Then, the number of subarrays not containing \(i\) equals

(the number of subarrays whose left end is \(x_0+1\) or greater, and right end is \(x_1-1\) or less)

\(+\) (the number of subarrays whose left end is \(x_1+1\) or greater, and right end is \(x_2-1\) or less)

\(\ldots +\) (the number of subarrays whose left end is \(x_{C_i}+1\) or greater, and right end is \(x_{C_i+1}-1\) or less).

This can be evaluated in \(\mathrm{O}(C_i)\) time. Hence, the problem has been solved.