Triplets of different numbers P35586

Consider an array A[0..n−1]. Given two indices ℓ and r of the array, can you count the number of triplets of different numbers in A[ℓ..r], that is, the number of (i, j, k) such that ℓ ≤ i < j < k ≤ r, A[i] ≠ A[j], A[j] ≠ A[k], and A[i] ≠ 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⁵. Follow the n ‍integer numbers A[0], …, A[n−1] of the array, all between 0 and 10⁹. Follow n different queries, each with an ℓ and an r such that 0 ≤ ℓ, ℓ + 2 ≤ 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.