B. Хамгийн их тэнэглэл

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

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

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

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

Шинэчлэлт Берландад үргэлжлэн явагдсаар байв. Жишээлбэл Берландын парламентын өчигдрийн хурлаар $n$ хууль батласан (эдгээр нь 1-ээс $n$ хүртэлх цорын ганц тоогоор тэмдэглэгдсэн байна). Өнөөдөр Берландын ерөнхийлөгч Г.В. Бүүсш-ын гарын үсгийг эдгээр хуулиуд дээр зуруулахаар тэдгээрийг түүний ширээн дээр авчирсан байв.

Энэ удаа Ноён Бүүсш $2k$ ширхэг хууль дээр гарын үсгээ зурахаар төлөвлөжээ.Тэрээр $k$ урт бүхий 1-ээс $n$ хүртэлх бүхэл тоонуудын үл огтлолцох яг 2 сегмент сонгох ба дугаар нь эдгээр сегментүүдэд байх хуулиуд дээр гарын үсгээ зурах юм. Илүү дэлгэрэнгүй хэлбэл Ноён Бүүсш 2 бүхэл тоо $a$, $b$ $(1 ≤ a ≤ b ≤ n - k + 1, b - a ≥ k)$ сонгох ба дугаарууд нь $[a; a + k - 1]$ болон $[b; b + k - 1]$ сегментүүд дээр орших бүх хуулиуд дээр гарын үсгээ зурна (сегментийн захад байгаа тоонууд нь мөн орно).

Ноён Бүүсш хуулиуд дээр гарын үсгээ зурах учраас мэдээж хэрэг тэрээр олон нийтийн санал бодлыг бодолцох юм. Бүхберландын олон нийтийн санал бодлын судалгааны төв (БОНСБСТ) иргэдийн дунд олон нийтийн санал асуулга явуулсан ба үр дүнгийн тайланг ерөнхийлөгчид өгчээ. Уг тайлан нь олон нийтийн санал бодлоор хууль бүрийн тэнэглэлийн утгыг агуулна. Ноён Бүүсш үнэхээр эх оронч хүн учраас тэрээр хамгийн их нийт тэнэглэлтэй хуулиуд дээр гарын үсгээ зурах сонирхолтой байгаа юм. Түүнд тусална уу.

Оролт

Эхний мөрөнд харгалзан парламентын баталсан хуулийн тоо болон нэг сегментийн уртыг илэрхийлэх 2 бүхэл тоо $n$ болон $k$ ($2 ≤ n ≤ 2*10^{5}$, $0 < 2k ≤ n$) өгөгдөнө. Дараагийн мөрөнд $n$ ширхэг бүхэл тоо $x_{1}, x_{2}, ..., x_{n}$ өгөгдөх ба эдгээр нь хууль тус бүрийн тэнэглэлийн утгыг илэрхийлнэ ($1 ≤ x_{i} ≤ 10^{9})$.

Гаралт

Сегментүүдийн эхлэл болох Ноён Бүүсш-ын сонгох ёстой 2 бүхэл тоо $a$, $b$-г хэвлэнэ. Энэ нь ерөнхийлөгч $[a; a + k - 1]$ болон $[b; b + k - 1]$ сегментүүд доторх дугааруудтай хуулиуд дээр гарын үсэг зурна гэсэн үг юм. Хэрэв олон тооны хариулт байвал та хамгийн бага $a$-ын утгатай хариултыг хэвлэнэ үү. Хэрэв ийм хариулт олон байвал хамгийн бага $b$-ын утгатай хариултыг хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
5 2
3 6 1 1 6
Гаралт
1 4
Оролт
6 2
1 1 1 1 1 1
Гаралт
1 3

Тэмдэглэл

Эхний жишээнд Ноён Бүүсш [1;2] болон [4;5] сегментүүд доторх дугааруудтай хуулиуд дээр гарын үсэг зурах юм. Ингэснээр нийт тэнэглэл нь $3 + 6 + 1 + 6 = 16$ байна.

2-дахь жишээнд Ноён Бүүсш [1;2] болон [3;4] сегментүүд доторх дугааруудтай хуулиуд дээр гарын үсэг зурах юм. Ингэснээр нийт тэнэглэл нь $1 + 1 + 1 + 1 = 4$ байна.

Сэтгэгдлүүдийг ачааллаж байна...