Triplets of different numbers P35586

Consider an array $A[0..n-1]$. Given two indices $\ell$ and $r$ of the array, can you count the number of triplets of different numbers in $A[\ell..r]$, that is, the number of $(i, j, k)$ such that $\ell \le i < j < k \le r$, $A[i] \ne A[j]$, $A[j] \ne A[k]$, and $A[i] \ne A[k]$? You will have to efficiently answer $n$ such questions.

Input

Input consists of several cases. Each case starts with an $n$ between 5 and $10^5$. Follow the $n$ integer numbers $A[0]$, …, $A[n-1]$ of the array, all between 0 and $10^9$. Follow $n$ different queries, each with an $\ell$ and an $r$ such that $0 \le \ell$, $\ell + 2 \le r$, and $r < n$.

Output

For every query of each case, print the required answer in a line (be aware that this answer may be large). Print a line with four dashes at the end of each case.

Observation

The expected solution solves three maximum cases in about two seconds.