Masala A

Qadim zamonlarda bir sarkarda Jasur haqida afsona mavjud. U o‘z bahtini sinab ko‘rmoqchi bo‘lib, sehrli yo‘lga safarga chiqadi.
Bu yo‘l uzunligi \(N\) bo‘lib, uning har bir nuqtasida qadimiy sandiq joylashgan.

Har bir sandiq oltin bilan to'la, bu oltinlar soni quyidagicha:

\(a_1, a_2, \ldots, a_N\)

Sarkarda Jasur yo‘ldan o‘tib ketayotib, ketma-ket joylashgan biron segmentdagi sandiqlarni ochish huquqiga ega.

Lekin, antik qoidaga ko‘ra faqat quyidagi shartlar bajarilgandagina sandiqlarni ochishi mumkin:

• Tanlangan segmentdagi oltinlarning jami \(K\) dan oshmasligi kerak;
• Tanlangan segmentda eng ko‘p oltin va eng oz oltin bor sandiqlar orasidagi farq \(D\) dan katta bo‘lmasligi kerak.

Jasur, barcha shartlarga mos eng uzun ketma-ket segment uzunligini aniqlashni istaydi.

Unga bu masalada yordam bera olasizmi?

Birinchi qatorda uchta butun son beriladi:

\(N,\ K,\ D\)

Ikkinchi qatorda esa \(N\) ta butun son:

\(a_1, a_2, \ldots, a_N\)

\(1\leq N \leq 2\times 10^5\)
\(1\leq a_i \leq 10^9\)
\(1\leq K \leq 10^{18}\)
\(0\leq D \leq 10^9\)

Subtask 1: N ≤ 30
Subtask 2: N ≤ 2000
Subtask 3: N ≤ 2*10^5, D = 10^9
Subtask 4: N ≤ 2*10^5, D = 0
Subtask 5: qo`shimcha cheklovlarsiz

Bitta butun son chiqaring — Jasur ochishi mumkin bo‘lgan eng uzun segment uzunligini.