Eng katta so'rovlar yig'indisi

$n$ ta sondan iborat massiv va $q$ ta so'rov $(l_i, r_i)$ berilgan. So'rov javobi — $a_{l_i} + \ldots + a_{r_i}$. So'rovlar berilmasdan oldin massiv elementlarining o'rnini istalgancha almashtirish mumkin. Barcha so'rovlar javoblari yig'indisining eng katta qiymatini toping.

Birinchi qatorda $n$ va $q$ ($1 \le n, q \le 2 \cdot 10^5$). Ikkinchi qatorda ta butun son (). Keyingi ta qatorning har birida so'rov: ikkita butun son va ().

Bitta son — eng katta jami yig'indi.

$i$-o'rin nechta so'rovga kirishini $f_i$ deb belgilang — uni farq massivi bilan $O(n + q)$ da topish mumkin. Jami yig'indi $\sum$, demak eng katta sonni eng ko'p ishlatiladigan o'ringa qo'yish kerak: va ni alohida saralab, mos elementlarni ko'paytiring.