We will solve the task using the offline method, where we first input all queries, and then process them. To begin with, let's define two functions, ~left(x)~, ~right(x)~ that correspond to the position of the first left and the first right element, respectively, of the same value as the one at position ~x~. These two functions are easily computed, traversing from left to right, or from right to left, keeping track of the 'latest' of each value using a hash map, structure map in C++ or a normal matrix, if we first compress the values. Let's observe a query ~[L, R]~ and functions ~left(x)~, ~right(x)~. It is easily noticed that we will count in a position ~x~ for query ~[L, R]~ if ~left(x) < L \le x \le right(x) \le R < right(right(x))~. Using natural language: we want the first left appearance of the value to be before the left end of the interval, and the first right appearance before or at the right end of the interval, in addition that there is no other occurrence of the value in the interval. With this, we ensure the counting of each pair of two identical values exactly once. Now the task is reduced to the following problem: for an ~x~, increment by ~1~ the solution of each query where ~left(x) < L \le x~ and where ~right(x) \le R < right(right(x))~.

In order to execute this query, we need to construct a tournament data structure over all intervals in the following way: for each node of the tournament that covers interval ~[A, B]~, we need to 'insert' the query ~[L, R]~ if ~A \le L \le R~, in other words, ~L \in [A, B]~. After this, for each ~x~, we need to insert the interval ~[right(x), right(right(x)))~ into all nodes of the tree of which the interval ~(left(x), x]~ is made of (typical query or update operation in a tournament data structure). There are ~\mathcal O(\log N)~ such nodes for each ~x~. After inserting queries and intervals into the tournament, we need to calculate the 'contribution' of each node to the queries located in that node. We perform this using the sweep technique and leave the implementation details as an exercise for the reader.

The total complexity of the given solution is ~\mathcal O(N \log^2 N)~. A solution of the complexity ~\mathcal O(N \log N)~ also exists, and is also left as an exercise for the reader.