Contest Duration: - (local time) (100 minutes) Back to Home
G - Triple Index /

Time Limit: 3 sec / Memory Limit: 1024 MB

問題文

q = 1, 2, \ldots, Q のそれぞれについて、q 番目のクエリでは整数の 2 つ組 (l_q, r_q) が与えられるので、

• l_q \leq i \lt j \lt k \leq r_q
• A_i = A_j = A_k

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5
• 1 \leq l_q \leq r_q \leq N
• 入力はすべて整数

入力

N Q
A_1 A_2 \ldots A_N
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q


出力

Q 行出力せよ。 q = 1, 2, \ldots, Q について、q 行目には q 番目のクエリに対する答えを出力せよ。

入力例 1

10 4
2 7 1 8 2 8 1 8 2 8
1 10
1 9
2 10
5 5


出力例 1

5
2
4
0


1 番目のクエリについて、問題文中の 2 つの条件をともに満たす整数の 3 つ組 (i, j, k) は、 (1, 5, 9), (4, 6, 8), (4, 6, 10), (4, 8, 10), (6, 8, 10)5 個です。

入力例 2

20 10
2 2 2 2 1 1 2 2 1 1 1 2 1 2 1 2 2 1 2 1
12 16
17 18
12 18
4 9
13 13
2 5
6 13
2 14
7 14
8 12


出力例 2

1
0
5
2
0
1
11
55
8
1


Score : 600 points

Problem Statement

You are given a length-N sequence (A_1, A_2, \ldots, A_N) of positive integers, and Q queries about the sequence.

For each q = 1, 2, \ldots, Q, the q-th query gives you an integer pair (l_q, r_q);
print the number of integer triplets (i, j, k) such that

• l_q \leq i \lt j \lt k \leq r_q, and
• A_i = A_j = A_k.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5
• 1 \leq l_q \leq r_q \leq N
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q


Output

Print Q lines. For q = 1, 2, \ldots, Q, the q-th line should contain the answer to the q-th query.

Sample Input 1

10 4
2 7 1 8 2 8 1 8 2 8
1 10
1 9
2 10
5 5


Sample Output 1

5
2
4
0


For the first query, there are five triplets of integers that satisfy the conditions in the problem statement: (1, 5, 9), (4, 6, 8), (4, 6, 10), (4, 8, 10), and (6, 8, 10).

Sample Input 2

20 10
2 2 2 2 1 1 2 2 1 1 1 2 1 2 1 2 2 1 2 1
12 16
17 18
12 18
4 9
13 13
2 5
6 13
2 14
7 14
8 12


Sample Output 2

1
0
5
2
0
1
11
55
8
1