Энг катта сўровлар йиғиндиси

$n$ та сондан иборат массив ва $q$ та сўров $(l_i, r_i)$ берилган. Сўров жавоби — $a_{l_i} + \ldots + a_{r_i}$. Сўровлар берилмасдан олдин массив элементларининг ўрнини исталганча алмаштириш мумкин. Барча сўровлар жавоблари йиғиндисининг энг катта қийматини топинг.

Биринчи қаторда $n$ ва $q$ ($1 \le n, q \le 2 \cdot 10^5$). Иккинчи қаторда $n$ та бутун сон ($1 \le a_i \le 2 \cdot 10^5$). Кейинги $q$ та қаторнинг ҳар бирида сўров: иккита бутун сон $l$ ва $r$ ($1 \le l \le r \le n$).

Битта сон — энг катта жами йиғинди.

$i$-ўрин нечта сўровга киришини $f_i$ деб белгиланг — уни фарқ массиви билан $O(n + q)$ да топиш мумкин. Жами йиғинди $\sum f_i \cdot a_{\text{жой}}$, демак энг катта сонни энг кўп ишлатиладиган ўринга қўйиш керак: $f$ ва $a$ ни алоҳида саралаб, мос элементларни кўпайтиринг.

Биринчи мисолда $f = (2, 3, 2)$: $5$ ўртага, жавоб $5 \cdot 3 + 3 \cdot 2 + 2 \cdot 2 = 25$. Жавоб $8 \cdot 10^{15}$ гача етади — 64 битли тур керак.

Манба: Codeforces, 276C-масала.