C. Бяцхан охин ба хамгийн их нийлбэр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан охин массив дээр хүсэлт боловсруулдаг бодлогуудад маш их дуртай.

Тэрээр энэ удаа түгээмэл байдаг нэгэн бодлоготой таарчээ: түүнд $n$ элементтэй массив байна (массивын элементүүд нь 1-ээс эхлэн дугаарлагдана); мөн $q$ тооны хүсэлт байх ба хүсэлт тус бүр нь $l_{i}$, $r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ n)$ гэсэн хос бүхэл тоогоор тодорхойлогдоно. Та хүсэлт бүрийн хувьд $l_{i}$-ээс $r_{i}$-ын хүртэлх ($l_{i}$ болон $r_{i}$ нь өөрсдөө орно) дугаартай элементүүдийн нийлбэрийг олох ёстой.

Бяцхан охинд энэ бодлого их уйтгартай санагдсан тул тэрээр хүсэлтүүдийг боловсруулахаасаа өмнө хүсэлтийн хариунуудын нийлбэр нь боломжит хамгийн их утгатай гарахаар массивын элементүүдийн байрлалыг өөрчлөхөөр шийдэв. Та энэхүү хамгийн их нийлбэрийн утгыг олно уу.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан $n$ ($1 ≤ n ≤ 2 \cdot 10^{5}$) болон $q$ ($1 ≤ q ≤ 2 \cdot 10^{5}$) гэсэн хоёр бүхэл тоог агуулах ба эдгээр нь массив дахь элементүүдийн тоо болон хүсэлтүүдийн тоог тус тус илэрхийлнэ.

Дараагийн мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг $a_{i}$ ($1 ≤ a_{i} ≤ 2 \cdot 10^{5}$) бүхэл тоо байх ба эдгээр нь массивын элементүүдийг илэрхийлнэ.

Дараагийн $q$ мөрөнд, мөр тус бүрд хүсэлтийг илэрхийлэх зайгаар тусгаарлагдсан $l_{i}$, $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) гэсэн хоёр бүхэл тоо байна.

Гаралт

Массивын элементүүдийн байрлалыг өөрчилсний дараа хүсэлтийн хариунуудын нийлбэр хамгийн ихдээ хэд байхыг харуулсан ганц тоог хэвлэнэ үү.

C++ дахь 64 бит бүхэл тоог унших болох бичихдээ %lld нарийвчлал ашиглахгүйг анхаарна уу. Үүний оронд cout хэсгийг ашиглах нь зүйтэй (мөн %I64d$ ашиглаж болно).

Орчуулсан: Энхгэрэл

Жишээ тэстүүд

Оролт
3 3
5 3 2
1 2
2 3
1 3
Гаралт
25
Оролт
5 3
5 2 4 1 3
1 5
2 3
2 3
Гаралт
33
Сэтгэгдлүүдийг ачааллаж байна...