Given a sequence $a_1, \dots, a_n$ and $m$ queries, each query provides $l$ and $r$. For each query, find the number of triples $(i, j, k)$ such that $l \le i < j < k \le r$ and $a_i = a_k > a_j$.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers $a_1, \dots, a_n$.

The next $m$ lines each contain two integers $l$ and $r$, representing a query.

Output

Output $m$ lines, each containing an integer representing the answer to the corresponding query.

Examples

Input 1

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

Output 1

4
4
1
0
0

Subtasks

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

All values are integers.

For $100\%$ of the data, $1 \le a_i \le n$, $1 \le l \le r \le n$, and $n, m \le 5 \times 10^5$.