D. Нууц биш шифр

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

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

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

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

Бэрланд Флатландтай хийж буй дайнд шинэлэг санаа олжээ. Дайсныг газар нутгаасаа хөөхийн тулд Бэрландчууд яг хэдэн цэрэг үлдсэнг мэдэх шаардлагатай. Азаар тагнуул тэдэнд тун хэрэгтэй байсан нууц захидал авч явсан дайсныг өглөөгүүр олзолжээ.

Олзлогдсон дайсанд эерэг бүхэл тоон массив байсан. Бэрландийн ухаантан Флатландын кодыг тайлдаг ба тэрхүү $m$ тоо агуулсан кодыг тайлахын тулд дайснууд $a$ гэсэн массив ашигладаг. Түүний дор хаяж $k$ ижил элемент агуулсан дэд массивийн тоо нь $m$ юм. $k$ тоог Бэрландын арми мэддэг байна. Тиймээс Генерал Туристов дахин Васиаг энэ асуудлыг шийдэхийг хүсэв (Флатландэрийн захиаг тайлах).

Васиад туслан бүхэл тоон $a$ массив болон $k$ тоо өгөгдсөнөөр дор хаяж $k$ ширхэг элемент нь хоорондоо тэнцүү байх $a$-ийн дэд массивийн тоог олно уу.

$a = (a_{1}, a_{2}, ..., a_{n})$ -ийн дэд массив $a[i... j]$ $(1 ≤ i ≤ j ≤ n)$-нь $i$ -ээс эхлэн $j$ дэх дараалсан элемент бүхий массив юм. $a[i... j] = (a_{i}, a_{i + 1}, ..., a_{j})$.

Оролт

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

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

Гаралт

дор хаяж $k$ ширхэг элемент нь хоорондоо тэнцүү байх $a$ ийн дэд массивийн тоог хэвлэ.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Бат-Од

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

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

Тэмдэглэл

Эхний жишээндэх боломжит дэд массивууд нь (1,2,1), (2,1,2) and (1,2,1,2).

Хоёрдахь жишээндэх боломжит дэд массивууд нь (1,2,1,1,3) and (1,2,1,1).

Гуравдахь жишээндэх боломжит дэд массивууд нь (1), (1), (1), (1,1), (1,1) and (1,1,1).

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