D. Тууз

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

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

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

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

Александрад байгаа цаасан туузан дээр нь нийтдээ $n$ ширхэг тоонууд цувруулан бичигдсэн байгаа бөгөөд бид тоонуудыг зүүнээс баруун тийш нь дугаарлаад $a_{i}$ гэж тэмдэглэе.

Александра цаасан туузыг дундуур нь хэсэгчлэн урж хэдэн хэсэг болгохыг хүссэн (урахгүй $1$ хэсэг хэвээр нь үлдээж болно). Гэхдээ хэсэг бүрийн хувьд дараах нөхцлүүд биелэх ёстой:

  • Хэсэг бүр хамгийн багадаа $l$ ширхэг тоо агуулах ёстой.
  • Хэсэг дэх хамгийн их тоо ба хамгийн бага тоонуудын хоорондын зөрүү нь хамгийн ихдээ $s$ байх ёстой.

Дээрх нөхцлийг хангасан хамгийн цөөн хэсэгт хуваахад Александрад тусална уу.

Оролт

Эхний мөрөнд зайгаар тусгаарласан гурван бүхэл $n, s, l$ ($1 ≤ n ≤ 10^{5}, 0 ≤ s ≤ 10^{9}, 1 ≤ l ≤ 10^{5}$) тоонууд агуулагдана.

Хоёр дахь мөрөнд $n$ ширхэг зайгаар тусгаарласан $a_{i}$ ($-10^{9} ≤ a_{i} ≤ 10^{9}$) тоонууд агуулагдана.

Гаралт

Хуваагдсан хэсгийн тоог хэвлэнэ.

Хэрвээ туузыг хуваах ямар арга байхгүй бол -1 гэж хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
7 2 2
1 3 1 2 4 1 2
Гаралт
3
Оролт
7 2 2
1 100 1 100 1 100 1
Гаралт
-1

Тэмдэглэл

Эхний жишээнд, бид туузыг $3$ хэсэгт хувааж чадна: $[1, 3, 1], [2, 4], [1, 2]$.

Хоёр дахь жишээнд, аль ч хэсэгт $1$ ба $100$ тоонууд хамт байвал нөхцөл биелэгдэхгүй бөгөөд энэ хоёр тоо цуг ороогүй хэсгүүдэд хуваах боломжгүй тул шийдгүй.

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