GR-M12. Marafon

Marafon yo‘li L km. Startda (0 km) yuguruvchi suv ichadi, shundan keyin suvsiz ko‘pi bilan D km yugura oladi. Yo‘lda n ta suv punkti bor (x₁ < x₂ < … < xₙ km), har birida to‘xtab, suv ichib, yana D km yugurish mumkin. Marraga (L km) yetish uchun eng kamida nechta punktda to‘xtash kerak? Iloji bo‘lmasa — -1.

Kirish ma’lumotlari

Birinchi qatorda n, L, D. Ikkinchisida n ta punkt (o‘sish tartibida).

Chiqish ma’lumotlari

Bitta son — to‘xtashlar soni yoki -1.

Cheklovlar

1 ≤ n ≤ 2·10⁵; 0 < xᵢ < L ≤ 10⁹; 1 ≤ D ≤ 10⁹.