B. Хашаа

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

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

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

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

Поликарпусийн гэрийн урд хашаа байдаг. Хашаа $n$ ширхэг ижил өргөнтэй нэг нь нөгөөгийхөө араас зүүнээс баруун тийш цувж байрласан банзнуудаас бүтдэг. $i$ дэх банзны өндөр $h_i$ метр, өөр банзнууд өөр өндөртэй байж болдог байна.

Зураг: $n = 7$ ба $h = [1, 2, 6, 1, 1, 7, 1]$ тохиолдол

Поликарпус дээд зэрэглэлийн төгөлдөр хуур худалдаж авсан ба үүнийгээ гэртээ хэрхэн оруулах талаар бодож байна. Төлөвлөгөөгөө гүйцэлдүүлэхийн тулд тэрээр хашаанаасаа $k$ ширхэг дараалласан банзнуудыг авах хэрэгтэй болно. Өндөр банзнуудыг хашаанаас салгаж авахад илүү хэцүү болохоор Поликарпүс өндрүүдийн нийлбэр нь байж болох хамгийн бага утга бүхий дараалласан $k$ ширхэг банзнуудыг олохыг хүсч байлаа.

Нийт өндрийн хэмжээ нь хамгийн бага байдаг $k$ ширхэг дараалласан хашаануудын индексүүдийг олдог програм бичээрэй. Хашаа Поликарпүсийн гэрийг тойроод биш гэрийнх нь урд байдгийг анхааруулъя (өөрөөр хэлбэл хашаа тойрог биш).

Оролт

Оролтын эхний мөрөнд $n$ болон $k$ ($1 ≤ n ≤ 1.5·10^5$, $1 ≤ k ≤ n$) гэсэн хашааны банзнуудын тоо болон төгөлдөр хууранд зориулж гаргах нүхний өргөнг илэрхийлэх 2 ширхэг бүхэл тоо байна. 2 дахь мөрөнд хашааны $i$ дэх банзны өндөр $h_i$ байхаар $h_1, h_2, ... , h_n$ ($1 ≤ h_i ≤ 100$) бүхэл тоонуудын дарааллууд байна.

Гаралт

$j, j+1, ... , j+k-1$ банзнуудын өндрийн нийлбэр нь боломжит хамгийн бага утгатай байх $j$-г хэвлэ. Ийм хэд хэдэн $j$ байвал тэдний аль нэгийг нь хэвлээрэй.

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

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

Оролт
7 3
1 2 6 1 1 7 1
Гаралт
3

Тэмдэглэл

In the sample, your task is to find three consecutive planks with the minimum sum of heights. In the given case three planks with indexes 3, 4 and 5 have the required attribute, their total height is 8.

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