ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2135. Полина и коммиты

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ
Полина работает в компании «Тындекс». Сегодня менеджер проекта назначил ей целых n заданий, но это не огорчило Полину, ведь она пишет код быстро и без ошибок, а единственное, что замедляет её — необходимость коммитить выполненные задания. Коммит — это сохранение изменений в коде в системе контроля версий.
В «Тындексе» действуют строгие правила относительно содержания коммитов: не разрешается коммитить после изменения каждой строчки кода, с другой стороны, коммиты должны быть небольшими и логически однородными. Чтобы формализовать эти требования, каждому заданию был сопоставлен коэффициент изменения кода — целое число от 1 до 109. Коммит считается хорошим, если произведение коэффициентов изменения кода заданий, входящих в коммит, принадлежит отрезку [l; r]. Также не разрешается коммитить частично выполненное задание.
Полина должна выполнять задания по очереди, то есть сделать первые несколько заданий, затем закоммитить изменения, потом сделать следующие несколько заданий, снова закоммитив изменения, и так далее. Поэтому Полину интересует минимальное количество хороших коммитов, достаточное для выполнения всех заданий. Поможете Полине?

Исходные данные

В первой строке даны целые числа n, l, r (1 ≤ n ≤ 50000; 1 ≤ lr ≤ 1018) — количество заданий и ограничения на произведение коэффициентов изменения кода соответственно.
В следующей строке дано n целых чисел — коэффициенты изменения кода заданий. Все коэффициенты — целые числа от 1 до 109.

Результат

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

Примеры

исходные данныерезультат
7 8 20
2 4 8 16 1 3 5
4
7 10 20
2 4 8 16 1 3 5
-1

Замечания

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