Cho dãy ~a~ gồm ~n~ phần tử và ~q~ truy vấn, mỗi truy vấn gồm 2 chỉ số ~l~ và ~r~. Với mỗi truy vấn, đếm số cặp ~(i, j)~ sao cho ~l <= i < j <= r~ và ~a[i]=a[j]~.

• ~n ≤ 10^5~
• ~q ≤ 10^4~
• ~a[i] ≤ 10^6~

Kết quả: ~q~ dòng, mỗi dòng in ra số cặp ~(i, j)~ thỏa mãn.

Ví dụ:

Input

5
1 2 2 1 1
5
1 2
2 3 
2 5
1 5
4 5

Output

0
1
2
4
1