Archiwum zadań programistycznych WWSI

W pewnym mieście znanym z zadań Demonstracja 2 i Metro płonie most. Strażacy podzielili most na n odcinków i dla każdego z nich określili siłę występującego na nim pożaru. Akcja gaśnicza będzie prowadzona z powietrza. Samolot będzie przelatywał wzdłuż mostu i zrzucał wodę na jeden wybrany odcinek. Po każdym takim zrzucie wody siła pożaru na wybranym odcinku maleje o w₁ jednostek, zaś na wszystkich pozostałych odcinkach o w₂ jednostek. Pożar zostanie ugaszony, w momencie kiedy na wszystkich odcinkach mostu jego siła będzie mniejsza bądź równa zeru.

Odpowiedz na pytanie ile minimalnie lotów będą musieli wykonać strażacy żeby ugasić pożar mostu?

Wejście

W pierwszej linii wejścia znajdują się trzy liczby całkowite n ∈ [1;10⁵], w₁ ∈ [1;10⁹] i w₂ ∈ [1;w₁] opisane powyżej. W kolejnej linii znajduje się n liczb całkowitych z przedziału [1;10⁹] oznaczających siłę pożaru na kolejnych odcinkach mostu.

Wyjście

Na wyjściu należy wypisać minimalną liczbę lotów jaką muszą wykonać strażacy, aby ugasić pożar.

Przykład

Wejście

4 2 1
1 2 3 2

Wyjście

2

Wyjaśnienie do przykładu

Przykładowy plan ugaszeniu pożaru może wyglądać następująco:

1. Zrzucamy wodę na 2 odcinek z lewej. Siła pożaru po zrzucie: 0 0 2 1
2. Zrzucamy wodę na 3 odcinek z lewej. Siła pożaru po zrzucie: 0 0 0 0