Masala #1027

Xotira 512 MB Vaqt 3000 ms
14

Maksimal segmentlar yig'indisi

Qulmamat massivdagi so'rovlar haqidagi masalalarni juda yaxshi ko'radi.

Bir kun u juda mashhur masalaga duch keldi. \(n\) ta elementli \(a\) massiv beriladi va \(q\) ta \(l_i,r_i(1\leq l_i\leq r_i\leq n)\) so'rovlar mavjud. Har bir so'rovda massivning \(l_i-\) elementidan \(r_i-\) elementigacha bo'lgan barcha sonlarning yig'indisini hisoblash talab etiladi.

Bunday vazifa Qulmamatga juda zerikarli tuyildi. U surovlarga javob berishidan oldin massiv elementlarini aralashtirib, barcha so'rovlarga javoblar yig'indisi maksimal darajaga keltirishga qaror qildi. Sizning vazifangiz ushbu maksimal miqdorni hisoblashdan iborat.


Kiruvchi ma'lumotlar:

Birinchi satrda ikkita \(n(1\leq n\leq 2000000)\) va \(q(1\leq q\leq 2000000)\) butun sonlar. Kiyingi satrda \(n\) ta \(a_i(-10^9\leq a_i\leq 10^9)\) massiv elementlari beriladi va kiyingi \(q\) satrda \(l_i,r_i(1\leq l_i\leq r_i\leq n)\) so'rovlari beriladi.


Chiquvchi ma'lumotlar:

Yagona satrda masalani javobini \(-\) massiv elementlari tartibini o'zgartirganingizdan so'ng so'rovlarga javoblarning maksimal yig'indisini chop eting.


Misollar
# input.txt output.txt
1
3 2
2 3 5
1 2
2 3
15
Izoh:

Birinchi testda [2, 3, 5] massivni [2, 5, 3] ko'rinishiga keltirsangiz so'rovlar  \(a_{[1..2]}=2+5=7\) va \(a_{[2..3]}=5+3=8\) yig'indisi 15 ga teng.