Migrated from Lutece 2921 飞跃13号房

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

羊，在草地上；兔子，在沙漠地上；小白，在矿洞里；苦力怕，在你家的木地板上。每个种群都有每个种群适合的栖息地，直到史蒂夫出现了，他很暴力的破坏了一块地，限制了种群的活动范围，他们不得不进行"飞跃"，即迁徙，以去到同一种地上，找到更安全的地方。

现在有 $n$ 块地排成一排，第 $i$ 块地的地形用一个整数 $a_i$ 来表示，史蒂夫想在这 $n$ 块地中第 $l$ 块到第 $r$ 块（包括边界）上建家，他想知道建家完成后有多少种从他家左边到他家右边的迁徙路线，换言之，他想知道有多少个数对 $(p,q)$ 满足 $p \lt l, r \lt q, a_p=a_q$ ，好每天睡前数羊、数兔子、数小白和数苦力怕。

有的时候史蒂夫会对这个建家位置不满意，他会恢复原来的地形，然后换个新的 $l$ 和 $r$ ，你需要处理 $q$ 组询问。

Input

第一行一个整数 $n$ ，表示地的个数。

第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 块地的地形。

第三行一个整数 $q$ ，表示询问个数。

最后 $q$ 行每行两个数 $l$ 和 $r$ ，表示史蒂夫将在第 $l$ 块到第 $r$ 块（包括边界）上建家。

Output

输出共 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 组询问的答案。

Samples

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

0
1
2
0
1
0

Constraints

$1 \le n \le 10^5, 1 \le a_i \le n, 1 \le q \le 10^5, 1 \le l \le r \le n$。

Resources

2023 UESTC ICPC Training for Data Structures