ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Later is better than never

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Pauline and commits

Time limit: 2.0 second
Memory limit: 256 MB
Pauline works for the company named “Tyndex”. Today the project manager gave her n tasks, but it didn’t upset Pauline, because she writes her code quickly and without errors, and the only thing that slows her down is the need to to commit the completed tasks. Commit is the saving of a set of tentative changes in the code in the version control system.
In “Tyndex” there are strict rules which apply to the content of commits: it is not allowed to commit after changing each line of code; on the other hand, commits must be small and logically uniform. To formalize these requirements, each task was assigned a coefficient of code change (CCC) — an integer from 1 to 109. A commit is considered as good if the product of the CCCs, which is included in the commit, belongs to the segment [l; r]. Also, it is not allowed to commit a partly completed task.
Pauline should do the tasks in their order, which mean to do the first several tasks, then commit changes, then do the following several tasks, again commit the changes, and so on. Therefore, Pauline is interested in the minimum number of good commits, which would be enough for all tasks. Will you help Pauline?

Input

The first line contains integers n, l, r (1 ≤ n ≤ 50000; 1 ≤ lr ≤ 1018) that are the number of tasks and the limits for the product of the CCCs, respectively.
In the next line there are n integers that are the tasks' CCCs. All coefficients are integers from 1 to 109.

Output

If Pauline won’t be able to do all tasks and commit them, in a single line output “-1”.
Otherwise, in a single line output the minimum number of good commits which is enough to complete all tasks.

Samples

inputoutput
7 8 20
2 4 8 16 1 3 5
4
7 10 20
2 4 8 16 1 3 5
-1

Notes

In the first test sample, fragmentation into commits is as follows: 2 4 | 8 | 16 1 | 3 5.
Problem Author: Anna Khanova
To submit the solution for this problem go to the Problem set: 2135. Pauline and commits