Mediana

You are given a sequence of $N$ natural numbers $a_0, a_1, ..., a_{N - 1}$, all having values between $1$ and $N$.

On this sequence you may perform any number of operations (possibly $0$) of the type $(l, r)$, where $0 \leq l \leq r < N$. As a result of an operation $(l, r)$, the entire subsequence (contiguous subarray) $a_l, a_{l + 1}, ..., a_r$ is replaced, within the whole sequence, by just the lower median element$^1$ of that subarray.

$^1$ The lower median element of a sequence of $M$ numbers $v_0, v_1, ..., v_{M - 1}$ is the element on position $\lfloor \frac{M - 1}{2} \rfloor$ (indexing the sequence starting from $0$) after sorting the sequence (for example, the lower median element of the sequence $4, 1, 3, 2$ is $2$, and the lower median element of the sequence $2, 7, 5, 10, 1$ is $5$).

For a sequence $V$ obtained by applying the described operation (zero or more times) and a number $X$, we denote by $f(V, X)$ the maximum length of a contiguous subsequence of $V$ in which all numbers have the value $X$. Also, given the function $f(V, X)$, we denote by $answer_X$ the maximum value of this function for a given value $X$, considering all sequences $V$ that can be obtained by applying (possibly repeatedly, or not at all) the operation described above.

Requirement

Besides the given sequence $a$ of $N$ numbers, you are also given $Q$ queries $l_i, r_i$, where $0 \leq l_i \leq r_i < N$, for every $i$ from $0$ to $Q - 1$. For each query, you must find $\sum_{X=1}^{N} answer_X \cdot X$, considering only the subsequence $a_{l_i}, a_{l_i + 1}, ..., a_{r_i}$ of the given sequence as the sequence on which the operations are applied.

Implementation Details

You must implement a single function:

std::vector<int64_t> solve(int N, int Q, std::vector<int> a, 
                            std::vector<int> l, std::vector<int> r)

The solve function will be called by the judge at most $T$ times and receives as parameters:

• $N$: the length of the initial sequence;
• $Q$: the number of queries;
• $a$: the $N$ values of the initial sequence (indexed from $0$);
• $l$ and $r$: representing the endpoints of the $Q$ queries, indexed from $0$, query number $i$ being represented by the pair $l_i, r_i$;

and must return a sequence containing $\sum_{X=1}^{N} answer_X \cdot X$ for each of the $Q$ queries, in the order in which they are given.

Constraints

• $1 \leq T, N, Q \leq 100 \ 000$
• $1 \leq a_i \leq N$, for $0 \leq i < N$
• $0 \leq l_i \leq r_i < N$, for $0 \leq i < Q$
• Let $M$ denote the number of distinct values in the sequence $a$ ($1 \leq M \leq N$)
• Let $S_N$ denote the sum of all values of $N$ over the $T$ tests, $S_Q$ the sum of all values of $Q$ over the $T$ tests, and $S_{NQ}$ the sum of all products $N \cdot Q$ over the $T$ tests.
• $1 \leq S_N, S_Q \leq 100 \ 000$

Examples

input

2
5
2 1 4 2 5
2
0 4
0 2
5
1 2 2 1 1
2
1 4
0 4

output

14
7
6
7

Explanations

In the first example:

• For the first query, we apply operations on the whole sequence: $2, 1, 4, 2, 5$. Let's analyze the case for $X = 2$, where we want to obtain the longest possible contiguous subsequence consisting only of the value $2$. We can choose to apply an operation on the elements $a_1, a_2, a_3$ (i.e., the values $1, 4, 2$). After sorting this subsequence ($1, 2, 4$), the median element is $2$. Replacing the subsequence with its median, the sequence becomes $2, 2, 5$. We stop here, because we have obtained a contiguous subsequence containing all the initial occurrences of $2$. It is not necessary for the entire sequence to be turned into values of $2$, it is enough that we obtained a contiguous subsequence of length $2$ made up exclusively of this value. So, $answer_2 = 2$. The values $1, 4$ and $5$ cannot form subsequences longer than length $1$, so $answer_1 = 1$, $answer_4 = 1$, $answer_5 = 1$. The value $3$ does not occur at all ($answer_3 = 0$). The sum for the first query is: $1 \cdot 1 + 2 \cdot 2 + 0 \cdot 3 + 1 \cdot 4 + 1 \cdot 5 = 14$.
• For the second query, we restrict ourselves to the first $3$ elements: $2, 1, 4$. Here no value repeats, and by no operation can we obtain contiguous subsequences longer than $1$. Thus, $answer_1 = 1$, $answer_2 = 1$, $answer_4 = 1$, while for the rest of the values ($3$ and $5$) the answer is $0$. The sum for the second query is: $1 \cdot 1 + 1 \cdot 2 + 0 \cdot 3 + 1 \cdot 4 + 0 \cdot 5 = 7$.

For the second example, similarly, the answer to the first query is $6$, and to the second is $7$.