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^{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 ℓ 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.

Public test cases

**Input**

5 42 23 100 23 42 0 2 1 3 2 4 0 4 1 4 7 1 2 3 1 2 3 4 0 6 0 5 0 2 3 5 1 5 1 4 0 4 5 4 0 4 0 4 0 4 1 4 2 4 1 3 0 2

**Output**

1 0 1 4 2 ---- 20 8 1 1 4 2 4 ---- 0 0 0 0 0 ----

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++