# Triplets of different numbers P35586

Statement

thehtml

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 < kr, 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 105. Follow the n ‍integer numbers A[0], …, A[n−1] of the array, all between 0 and 109. 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