Given an integer sequence $A_1, A_2, \dots, A_n$ of length $n$, and $q$ queries, each query provides two integers $x$ and $y$. Find the number of integer pairs $(i, j)$ such that $1 \le i < j \le n$, $A_i = x$, and $A_j = y$.

Input

The first line contains two integers $n, q$ ($1 \le n, q \le 10^5$), representing the length of the sequence and the number of queries, respectively.

The second line contains $n$ integers $A_1, A_2, \dots, A_n$ ($1 \le A_i \le 10^9$), representing the given sequence.

The next $q$ lines each contain two integers $x, y$ ($1 \le x, y \le 10^9$), representing a query.

Output

Output $q$ lines, each containing one integer, representing the number of pairs $(i, j)$ such that $1 \le i < j \le n$, $A_i = x$, and $A_j = y$.

Examples

Input 1

11 3
3 1 4 1 5 9 2 6 5 3 5
3 5
1 3
4 8

Output 1

4
2
0

Note

For the first query, the 4 pairs satisfying the conditions are $(1, 5), (1, 9), (1, 11), (10, 11)$.

For the second query, the 2 pairs satisfying the conditions are $(2, 10), (4, 10)$.

For the third query, there are no pairs satisfying the conditions.