Space_accident — OOI qualification
Task type: batch | Time limit: 1 s | Memory limit: 256 MB | Difficulty: 22
Algorithms: large number arithmetic, mathematics, binary search

# Space accident

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 1 second        |
| Memory limit: | 256 megabytes   |

You are a member of the crew of the spaceship «Hyperion» and recently you were involved in a fierce space battle from which you miraculously escaped. However, the reactor of your spaceship has suffered serious damage and overheated, causing the emergency cooling system to activate.

The reactor of the spaceship consists of *n* independent blocks, each of which has its own temperature expressed as an integer in degrees. In order for it to function stable, each block must have a strictly negative temperature. Thanks to scientific advances, the cooling system cools *n* − 1 blocks by *B* degrees in one cycle, and one remaining block by *A* degrees.

The cooling system was not damaged, but due to the spaceship's computer being damaged, it cannot calculate the minimum number of cycles required to fully cool down the reactor. Only you can solve this challenging task.

### Input

The first line contains three integers *n*, *A* and *B* (1 ≤ *n* ≤ 100 000, 1 ≤ *A*, *B* ≤ 10<sup>9</sup>) — the number of blocks in the reactor and the parameters *A* and *B*.

The next line contains *n* integers *t*<sub>1</sub>, *t*<sub>2</sub>, . . . , *t*<sub>n</sub> (-10<sup>9</sup> ≤ *t*<sub>i</sub> ≤ 10<sup>9</sup>), where *t*<sub>i</sub> — the temperature of the *i*-th unit in the reactor.

### Output

Print a single number — the minimum number of cycles until the reactor is completely cooled.

### Examples

| Standard Input | Standard Output |
|----------------|-----------------|
| 5 1 2          | 3               |
| 1 2 3 4 5      |                 |
| 3 42 42        | 0               |
| -273 -273 -273 |                 |
| 1 3 2          | 4               |
| 9              |                 |
| 4 4 2          | 2               |
| 5 5 1 0        |                 |

### Note

In the fourth test case, the cooling system can cool the first block by 4 degrees on the first cycle, and the remaining blocks by 2 degrees each. As a result, the temperatures of the blocks will be as follows: {1, 3, −1, −2}. On the next cycle, the second block can be cooled by 4 degrees, after which the temperatures of all the blocks will become negative.

### Scoring

The tests for this problem consist of 6 groups. Points for each group are awarded only if all the tests in that group and some tests from the previous groups pass. Offline-testing means that the results of testing your solution on this group will only be available after the competition ends.

| Group | Score | Additional Constraints | Required Groups | Comment          |
|-------|-------|-----------------------|-----------------|------------------|
|       |       | n                     | *t*<sub>i</sub>               | A             | B             |                 |                  |
| 0     | 0     | –                     | –                | –             | –             | –               | Samples.         |
| 1     | 15    | n ≤ 5               | *t*<sub>i</sub> ≤ 5   | A ≤ 5   | B ≤ 5   | –               | –                |
| 2     | 16    | –                     | –                | A = 1      | B = 2      | –               | –                |
| 3     | 10    | –                     | –                | –             | –             | –               | A=B              |
| 4     | 15    | n = 2                 | –                | –             | –             | –               |                  |
| 5     | 24    | n ≤ 500         | *t*<sub>i</sub> ≤ 500 | A ≤ 500 | B ≤ 500 | 0, 1            | –                |
| 6     | 20    | –                     | –                | –             | –             | 0 – 5           | Offline-testing. |

Starter code: