First, for a fixed integer \(i\) between \(1\) and \(N\), let us consider the property of pairs \((L, R)\) with \(1 \leq L \leq R \leq N\) such that \(A_i\) appears exactly once in \(A_L, A_{L + 1}, \ldots, A_R\). Then, the following consequence follows:

• Take the largest integer \(j\) such that \(j < i\) and \(A_j = A_i\). If there is no such \(j\), let \(j = 0\).

• Take the smallest integer \(k\) such that \(i < k\) and \(A_i = A_k\). If there is no such \(k\), let \(k = N + 1\).

• The pairs \((L,R)\) with \(j < L \leq i\) and \(i \leq R < k\) are those that satisfy the condition.

Since the pairs \((L,R)\) that satisfy the original condition in the problem statement are the union of such pairs over \(i = 1,2, \ldots, N\). Thus, it suffices to solve the following problem:

Given \(N\) tuples of integers \((x_i,y_i,z_i,w_i)\), count integer pairs \((L, R)\) such that, \(x_i \leq L \leq y_i\) and \(z_i \leq R \leq w_i\) for some \(i\).

By the observation above, the given tuples always satisfy \(y_i = z_i\), but note that the discussion below does not use this property, and we do not impose such condition.

The problem above becomes clearer by rephrasing as follows:

There is a two-dimensional array \(B\) initialized with \(0\). Given \(N\) tuples of integers \((x_i, y_i, z_i, w_i)\), perform the following operation for each \(i\):

• add \(1\) to \(B_{l,r}\) for all integer pairs \((l,r)\) such that \(x_i \leq l \leq y_i\) and \(z_i \leq r \leq w_i\).

Count positive elements in the resulting \(B\).

The idea of sweep line algorithm enables further rephrasing:

There is a length-\(N\) sequence \(C\) initialized with \(0\). Initialize the answer with \(0\). Given \(N\) tuples of integers \((x_i, y_i, z_i, w_i)\), perform the following operation for each \(i = 1,2,\ldots, N\) in order:

• for each tuple of integers \((x_j, y_j, z_j, w_j)\) with \(x_j = i\), add \(1\) to \(C_{z_j}, C_{z_j + 1}, \ldots\), and \(C_{w_j}\).

• Count positive elements of \(C\), and add the count to the answer.

• For each tuple of integers \((x_j, y_j, z_j, w_j)\) with \(y_j = i\), subtract \(1\) from \(C_{z_j}, C_{z_j + 1}, \ldots\), and \(C_{w_j}\).

These procedure naively runs in \(\Theta(N^2)\) time, but one can use a lazy segment tree to optimize it to \(O(N \log N)\).

Specifically, it should maintains the minimum value and the number of its occurrences for each segment, and allows segment addition, in order to solve the problem.

Note that we only have to count elements with value \(0\) because the elements of \(C\) are always non-negative during the procedure, and we use the property that if \(C\) contains \(0\) as its element, then the minimum value of \(C\) is \(0\).

Bonus: finding the area of the union of rectangles is a famous and standard problem (cf. Library Checker).