Полина работает в компании «Тындекс». Сегодня менеджер проекта назначил ей целых n заданий, но это не огорчило Полину, ведь она пишет код быстро и без ошибок, а единственное, что замедляет её — необходимость коммитить выполненные задания. Коммит — это сохранение изменений в коде в системе контроля версий.

В «Тындексе» действуют строгие правила относительно содержания коммитов: не разрешается коммитить после изменения каждой строчки кода, с другой стороны, коммиты должны быть небольшими и логически однородными. Чтобы формализовать эти требования, каждому заданию был сопоставлен коэффициент изменения кода — целое число от 1 до 10⁹. Коммит считается хорошим, если произведение коэффициентов изменения кода заданий, входящих в коммит, принадлежит отрезку [l; r]. Также не разрешается коммитить частично выполненное задание.

Полина должна выполнять задания по очереди, то есть сделать первые несколько заданий, затем закоммитить изменения, потом сделать следующие несколько заданий, снова закоммитив изменения, и так далее. Поэтому Полину интересует минимальное количество хороших коммитов, достаточное для выполнения всех заданий. Поможете Полине?

В первой строке даны целые числа n, l, r (1 ≤ n ≤ 50000; 1 ≤ l ≤ r ≤ 10¹⁸) — количество заданий и ограничения на произведение коэффициентов изменения кода соответственно.

В следующей строке дано n целых чисел — коэффициенты изменения кода заданий. Все коэффициенты — целые числа от 1 до 10⁹.

Если Полина не сможет выполнить и закоммитить все задания, в единственной строке выведите «-1».

Иначе в единственной строке выведите целое число — минимальное количество хороших коммитов, достаточное для выполнения всех заданий.

В первом тестовом примере одним из оптимальных разбиений на коммиты является следующее: 2 4 | 8 | 16 1 | 3 5.