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?
The first line contains integers n, l, r (1 ≤ n ≤ 50000; 1 ≤ l ≤ r ≤ 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.
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.
7 8 20
2 4 8 16 1 3 5
7 10 20
2 4 8 16 1 3 5
In the first test sample, fragmentation into commits is as follows: 2 4 | 8 | 16 1 | 3 5.
Problem Author: Anna Khanova