Odd Length Subarray Mode Center

Given a sequence \( a \) of length \( n \) and \( m \) queries, consider the following definition. For a subarray \( [l, r] \) (using 1-indexing), a number \( x \) is called a mode of the subarray if and only if there does not exist any number \( y \) such that the number of occurrences of \( y \) in \( [l, r] \) is greater than the number of occurrences of \( x \) in \( [l, r] \).

Each query is given by two integers \( l \) and \( r \). Your task is to count the number of pairs \( (l', r') \) satisfying:

• \( l \leq l' \leq r' \leq r \);
• The length of the subarray \( [l', r'] \) is odd;
• If we denote \( c = \frac{l' + r'}{2} \) (note that \( c \) is an index, not the value \( a[c] \)), then the element \( a[c] \) is one of the modes of the subarray \( [l', r'] \).

Note that any odd-length subarray has a unique center and can be expressed in the form \( [c-k, c+k] \) for some non-negative integer \( k \). In such a subarray, you should verify that the frequency of \( a[c] \) is equal to the maximum frequency among all elements in \( [c-k, c+k] \). Count all such subarrays for each query.

inputFormat

The first line contains two integers \( n \) and \( m \), representing the length of the sequence and the number of queries.

The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \).

Each of the next \( m \) lines contains two integers \( l \) and \( r \) representing a query.

outputFormat

For each query, output a single integer in a new line — the number of subarrays \( [l', r'] \) (of odd length) within \( [l, r] \) such that if \( c = \frac{l' + r'}{2} \) then \( a[c] \) is a mode of \( [l', r'] \).

sample

5 1
1 2 1 2 1
1 5

6