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

1906. Исчезнувшая цивилизация

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Совсем недавно на одной из планет в системе Бетельгейзе были найдены руины древнего города. Особое внимание привлёк к себе неплохо сохранившийся храм, стены которого были исписаны многочисленными текстами. После расшифровки записей выяснилось, что они повествуют об общественном устройстве и культуре исчезнувшей цивилизации.
В частности, письмена сообщали о том, как во времена расцвета этой цивилизации было организовано производство и распределение пищи. Оказалось, что вокруг города располагались поля с каким-то съедобным растением, отличавшимся крайне высокой урожайностью. Осенью любой горожанин мог придти на любое такое поле и взять свою долю плодов. Эта доля была строго фиксирована, причём доли любых двух жителей города были равны. Никто не мог взять ни больше, ни меньше своей доли. Если кто-то, приходя на поле, обнаруживал, что там осталось меньше плодов, чем ему причитается, он ничего не брал и отправлялся на другое поле. Оставшиеся плоды пускали на семена, в результате чего из каждого из них на следующий год вырастало некоторое количество новых плодов. Это количество было всегда одинаковым и не зависело ни от года, ни от того, из какого плода были взяты семена.
Вы нашли рядом с тем местом, где когда-то находилось ближайшее к городу поле, пронумерованные таблички с некоторыми числами. Вы предположили, что на этих табличках вёлся ежегодный учёт плодов, оставшихся к началу зимы на этом поле, и что плодов на поле всегда оставалось меньше, чем размер одной доли. От года к году внешний вид табличек несколько менялся, и возможно, что более новые из них имели совершенно иное назначение. Определите наибольшее количество старых табличек, записи на которых не противоречат вашему предположению.

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

В первой строке записано целое число n — количество табличек (1 ≤ n ≤ 104). Во второй строке записаны целые числа a0, a1, …, an − 1, записанные на табличках (0 ≤ ai ≤ 109). На самой старой табличке записано число a0, на самой новой — an − 1.

Результат

Выведите целые числа L, P и k, означающие, что числа на L первых табличках не противоречат размеру доли P и коэффициенту прироста k. Числа P и k должны удовлетворять следующим ограничениям: 1 ≤ P ≤ 2 · 1018; 0 ≤ k ≤ 2 · 1018 (гарантируется, что среди решений задачи есть удовлетворяющее этим ограничениям). Если существует несколько решений с максимальным значением L, выведите любое из них.

Примеры

исходные данныерезультат
5
1 2 4 8 0
5 16 2
3
4 2 1
3 5 3
Автор задачи: Денис Дублённых
Источник задачи: XVI Открытый чемпионат Урала по спортивному программированию (апрель, 2012)