Problem Description

Given a sequence $a$ of length $n$, define $x$ to be the mode of the interval $[l, r]$ if and only if there does not exist $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 gives $l, r$. For each query, find how many ordered pairs $(l', r')$ satisfy $l \le l' \le r' \le r$, and the length of interval $[l', r']$ is odd, and $(l' + r') / 2$ (note that this is an index, not the value at that index) is the mode of the interval $[l', r']$.

Input Format

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

The next line contains $n$ integers describing the sequence.

The following $m$ lines each contain two integers $l$ and $r$, representing one query.

Output Format

Output $m$ lines in total, each being the answer for the corresponding query.

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

2
0
2
1
0
3
1
6
0
1

Hint

Idea: yummy&nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477&czr, Data: nzhtl1477(partially uploaded)

For $100\%$ of the testdata: $1 \le n, m \le 5 \times 10^5$, $1 \le l \le r \le n$, $1 \le a_i \le n$. All values are integers.

Sample explanation:

In $[1,4]$, the subintervals that satisfy the conditions are $[1,3]$, $[2,2]$.

In $[1,3]$, the subintervals that satisfy the conditions are $[1,3]$, $[2,2]$.

In $[2,6]$, the subintervals that satisfy the conditions are $[2,2]$.

In $[7,10]$, the subintervals that satisfy the conditions are $[7,7]$, $[8,10]$, $[10,10]$.

In $[4,10]$, the subintervals that satisfy the conditions are $[7,7]$, $[6,8]$, $[5,9]$, $[4,10]$, $[8,10]$, $[10,10]$.

In $[3,7]$, the subintervals that satisfy the conditions are $[7,7]$.

Translated by ChatGPT 5