Given a sequence $a$ of length $n$, $x$ is defined as the mode of an interval $[l, r]$ if and only if there is no $y$ such that the number of occurrences of $y$ in the interval $[l, r]$ is greater than the number of occurrences of $x$ in the interval $[l, r]$.

There are $m$ queries. Each query provides $l$ and $r$. Find the number of pairs $(l', r')$ such that $l \le l' \le r' \le r$, the length of the interval $[l', r']$ is odd, and $(l' + r')/2$ (note: this refers to the index, not the value at the index) is the mode of the interval $[l', r']$.

Input

The first line contains two integers $n$ and $m$. The next line contains $n$ integers representing the sequence. The next $m$ lines each contain two integers $l$ and $r$, representing a query. Constraints: $1 \le n \le 5 \times 10^5$, $1 \le m \le 10^6$, $1 \le l \le r \le n$, $1 \le a_i \le n$, and all values are integers.

Output

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

Examples

Input 1

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

Output 1

2
0
2
1
0
3
1
6
0
1

Note

For $[1, 4]$, the subintervals satisfying the condition are $[1, 3]$ and $[2, 2]$. For $[1, 3]$, the subintervals satisfying the condition are $[1, 3]$ and $[2, 2]$. For $[2, 6]$, the subinterval satisfying the condition is $[2, 2]$. For $[7, 10]$, the subintervals satisfying the condition are $[7, 7]$, $[8, 10]$, and $[10, 10]$. For $[4, 10]$, the subintervals satisfying the condition are $[7, 7]$, $[6, 8]$, $[5, 9]$, $[4, 10]$, $[8, 10]$, and $[10, 10]$. For $[3, 7]$, the subinterval satisfying the condition is $[7, 7]$.