Majority Subsegment Sum Query

You are given a sequence of integers \( a_1, a_2, \dots, a_n \) of length \( n \) and you need to answer \( m \) queries. Each query provides two integers \( l \) and \( r \). For each query, consider every contiguous subsegment \( [L, R] \) where \( l \le L \le R \le r \). For each such subsegment, for every integer \( c \) (where \( 1 \le c \le n \)), if the following condition holds:

\( R - L + 1 < 2\sum_{i=L}^{R} [a_i = c] \)

(Here \( [\mathrm{cond}] \) is the indicator function equal to 1 if the condition is true, and 0 otherwise.) Then the contribution of the subsegment is \( c \). The answer to the query is the sum of \( c \) for all \( c \) satisfying the condition over all subsegments \( [L, R] \) contained in \( [l, r] \).

Note: In other words, for each subsegment, if an integer appears strictly more than half the length of the subsegment, then add that integer to the answer (if more than one integer satisfies, add all of them, although at most one can be a majority in a subsegment).

inputFormat

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

The second line contains \( n \) space-separated integers \( a_1, a_2, \dots, a_n \).

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

outputFormat

For each query, output a single line containing the answer: the sum computed based on the subsegments within the given range as described in the problem.

sample

3 2
1 2 3
1 3
2 3

6
5