B. Шоронгийн шилжүүлэлт

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

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

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

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

Танай хотын шорон $n$ хоригдолтой. Бүх хоригдлыг байрлуулах боломжгүй болсон тул хотын дарга өөр шорон руу $c$ хоригдлыг шилжүүлхээр шийдсэн.

Уг шалтгаанаар $n$ хоригдлыг дугаараар нь нэг шугаманд жагсаасан. Энэ тоо нь хийсэн гэмт хэргийн түвшинөөс хамаарна. Илүү хүнд гэмт хэрэгтнүүд их тоотой байна.

Дараа нь хотын дарга өөр шорон руу явуулах $c$ хоригдлуудыг сонгосон. Тэр хоёр нөхцөл тавьсан. Эдгээр нь,

  • Сонгогдох $c$ хоригдлууд нь зэргэлдээ жагссан байх ёстой.
  • Бүх сонгогдох хоригдлуудын гэмт хэргийн түвшин нь $t$-ээс ихгүй байна. Учир нь хотын дарга шилжүүлэлтийн явцад ямар нэгэн эрсдэл гаргахыг хүсээгүй.

$c$ хоригдлуудыг хэдэн янзаар сонгож болох вэ?

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан гурван бүхэл
$n (1 ≤ n ≤ 2*10^{5})$, $t (0 ≤ t ≤ 10^{9})$, $c (1 ≤ c ≤ n)$ тоонууд байна. Дараагийн мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг тоо байна. Эдгээр бүхэл тоонууд нь тухайн хоригдлуудын гэмт хэргийн түвшинг илэрхийлнэ. Мөн эдгээр утгууд нь эсрэг биш $10^9$-өөс хэтрэхгүй.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ $c$ хоригдлуудыг сонгох боломжит тоо.

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

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

Оролт
4 3 3
2 3 1 1
Гаралт
2
Оролт
1 1 1
2
Гаралт
0
Оролт
11 4 2
2 2 0 7 3 2 2 4 9 1 4
Гаралт
6
Сэтгэгдлүүдийг ачааллаж байна...