Mediana

Se dă un șir de $N$ numere naturale $a_0, a_1, ..., a_{N - 1}$, toate având valori între $1$ și $N$.

Asupra acestui șir se pot executa oricâte operații (posibil $0$) de tipul ($l, r$), unde $0 \leq l \leq r < N$. În urma unei operații ($l, r$), toată subsecvența (subșir continuu) $a_l, a_{l + 1}, ..., a_r$ se înlocuiește în întregul șir doar cu elementul median inferior$^1$ al acesteia.

$^1$ Elementul median inferior al unui șir de $M$ numere $v_0, v_1, ..., v_{M - 1}$ este elementul de pe poziția $\lfloor \frac{M - 1}{2} \rfloor$ (indexând șirul de la $0$) după ce se sortează șirul (de exemplu, elementul median inferior al șirului $4, 1, 3, 2$ este $2$, iar elementul median inferior al șirului $2, 7, 5, 10, 1$ este $5$).

Pentru un șir $V$ obținut prin aplicarea operației descrise (de $0$ sau mai multe ori) și un număr $X$, notăm lungimea maximă a unei subsecvențe din șirul $V$ în care toate numerele au valoarea $X$ cu $f(V, X)$. De asemenea, având funcția $f(V, X)$, se notează cu $answer_X$ valoarea maximă a acestei funcții pentru o valoare $X$ dată, considerând toate șirurile $V$ ce pot fi obținute prin aplicarea (posibil repetată sau deloc) a operației descrise anterior.

Cerință

Pe lângă șirul $a$ de $N$ numere deja dat, se dau și $Q$ interogări $l_i, r_i$, unde $0 \leq l_i \leq r_i < N$, pentru orice $i$ de la $0$ la $Q - 1$. Pentru fiecare interogare se cere să se afle $\sum_{X=1}^{N} answer_X \cdot X$, considerând doar subsecvența $a_{l_i}, a_{l_i + 1}, ..., a_{r_i}$ din șirul dat drept șir pe care se aplică operațiile.

Detalii de implementare

Veți avea de implementat o singură funcție:

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

Funcția solve va fi apelată de către comisie de cel mult $T$ ori și primește ca parametri:

• $N$: lungimea șirului inițial;
• $Q$: numărul de interogări;
• $a$: cele $N$ valori ale șirului inițial (indexate de la $0$);
• $l$ și $r$: reprezentând capetele celor $Q$ interogări, indexate de la $0$, interogarea cu numărul $i$ fiind reprezentată de perechea $l_i, r_i$;

și trebuie să returneze un șir cu $\sum_{X=1}^{N} answer_X \cdot X$ pentru fiecare dintre cele $Q$ interogări, în ordinea în care acestea sunt date.

Restricții

• $1 \leq T, N, Q \leq 100 \ 000$
• $1 \leq a_i \leq N$, pentru $0 \leq i < N$
• $0 \leq l_i \leq r_i < N$, pentru $0 \leq i < Q$
• Se notează cu $M$ numărul de valori distincte din șirul $a$ ($1 \leq M \leq N$)
• Se notează cu $S_N$ suma tuturor valorilor lui $N$ din cele $T$ teste, cu $S_Q$ suma tuturor valorilor lui $Q$ din cele $T$ teste și cu $S_{NQ}$ suma tuturor produselor $N \cdot Q$ din cele $T$ teste.
• $1 \leq S_N, S_Q \leq 100 \ 000$

Exemple

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

Explicații

În primul exemplu:

• Pentru prima interogare, aplicăm operațiile pe întregul șir: $2, 1, 4, 2, 5$. Să analizăm cazul pentru $X = 2$, unde vrem să obținem o subsecvență continuă cât mai lungă formată doar din valoarea $2$. Putem alege să aplicăm o operație pe elementele $a_1, a_2, a_3$ (adică valorile $1, 4, 2$). După sortarea acestei subsecvențe ($1, 2, 4$), elementul median este $2$. Înlocuind subsecvența cu mediana ei, șirul devine $2, 2, 5$. Ne oprim aici, pentru că am obținut o subsecvență în care se află toate aparițiile inițiale ale lui $2$. Nu este nevoie ca întregul șir să fie transformat în valori de $2$, ci este suficient că am obținut o subsecvență continuă de lungime $2$ formată exclusiv din această valoare. Deci, $answer_2 = 2$. Valorile $1, 4$ și $5$ nu pot forma subsecvențe mai mari de lungime $1$, deci $answer_1 = 1$, $answer_4 = 1$, $answer_5 = 1$. Valoarea $3$ nu există deloc ($answer_3 = 0$). Suma pentru prima interogare este: $1 \cdot 1 + 2 \cdot 2 + 0 \cdot 3 + 1 \cdot 4 + 1 \cdot 5 = 14$.
• Pentru a doua interogare, ne restrângem la primele $3$ elemente: $2, 1, 4$. Aici nicio valoare nu se repetă și nu putem obține prin nicio operație subsecvențe mai lungi de $1$. Astfel, $answer_1 = 1$, $answer_2 = 1$, $answer_4 = 1$, iar pentru restul valorilor ($3$ și $5$) răspunsul este $0$. Suma pentru a doua interogare este: $1 \cdot 1 + 1 \cdot 2 + 0 \cdot 3 + 1 \cdot 4 + 0 \cdot 5 = 7$.

Pentru al doilea exemplu, în mod similar, răspunsul la prima interogare este $6$, iar la a doua este $7$.