B. Ваня ба хоол боловсруулагч

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

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

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

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

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

Ваня-д $n$ хэсэг төмс байгаа бөгөөд $i$-р хэсгийн өндөр нь $a_{i}$-тай тэнцүү байна. Тэрээр тэдгээрийг $1$ дугаартай хэсгээс эхлэн $n$ дугаартай хэсэг хүртэл нэг нэгээр нь хоол боловсруулагч уруу хийх юм. Тодорхой тайлбарлавал секунд болгонд дараах үйл явдал болно:

  1. Хэрэв дор хаяж нэг хэсэг төмс үлдсэн байвал Ваня дараагийн хэсэг төмсөнд хангалттай зай үлдэхгүй болох хүртэл тэдгээрийг хоол боловсруулагч уруу нэг нэгээр нь хийнэ.
  2. Хоол боловсруулагч нь $k$ сантиметр төмс бутална ($k$ сантиметрээс бага байвал өөрийн дотор байгаа бүх зүйлийг бутална).

Хоол боловсруулагчийн параметрын утга болон нэг мөрөнд байрлах төмс бүрийн хэмжээнүүдийн мэдээллийг ашиглан бүх төмсийг бутлахад шаардагдах хугацааг олно уу.

Оролт

Эхний мөрөнд харгалзана төмсний хэсгийн тоо, хоол боловсруулагчийн өндөр болон секунд болгонд бутлагдах төмсний хэмжээг илэрхийлэх бүхэл тоонууд $n$, $h$ болон $k$ ($1 ≤ n ≤ 100 000, 1 ≤ k ≤ h ≤ 10^{9}$) өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг бүхэл тоонууд $a_{i}$ ($1 ≤ a_{i} ≤ h$)-ууд өгөгдөх ба эдгээр нь төмсний хэсгүүдийн өндрүүдийг илэрхийлнэ.

Гаралт

Дээр дүрслэгдсэн үйл явцын дагуу бүх төмснүүдийг бутлахад шаардагдах секундийн тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

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

Тэмдэглэл

Эхний жишээг авч үзье.

  1. Эхлээд Ваня $5$ өндөртэй төмсний хэсгийг боловсруулагч уруу хийнэ. Секундийн дараа зөвхөн $2$ хэмжээтэй төмс боловсруулагч дотор үлдсэн байна.
  2. Одоо Ваня $4$ өндөртэй төмсний хэсгийг боловсруулагч уруу хийнэ. Өмнө нь үлдсэн $2$ хэмжээтэй төмс дээр нэмэгдэж байгааг анхаарна уу. Уг секундийн дараа $3$ хэмжээтэй төмс боловсруулагч дотор үлдсэн байна.
  3. Ваня $3$ өндөртэй төмсний хэсгийг дахин боловсруулагч уруу хийх ба уг секундийн төгсгөлд зөвхөн $3$ хэмжээтэй төмс боловсруулагч дотор үлдсэн байх юм.
  4. Ваня эцэст нь $2$ болон $1$ гэсэн өндөртэй хэсгүүдийг боловсруулагч уруу хийнэ. Уг секундийн төгсгөлд боловсруулагч доторх төмсний өндөр нь $3$-тай тэнцүү болох юм.
  5. Энэ секундийн турш боловсруулагч бүх төмсийг буталж дуусах ба ингэснээр уг үйл явц дуусна.

2-дахь жишээнд Ваня $5$ өндөртэй төмсний хэсгийг боловсруулагч уруу хийх ба уг төмс нь бутлагдаж дуустал $2$ секунд хүлээх юм. Дараа нь тэрээр үлдсэн $4$ хэсгүүдэд яг ижил үйлдлийг давтан хийх ба ингэснээр нийт хугацаа нь $2*5 = 10$ секунд болох юм.

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

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