Совсем недавно на одной из планет в системе Бетельгейзе были найдены
руины древнего города. Особое внимание привлёк к себе неплохо
сохранившийся храм, стены которого были исписаны многочисленными текстами.
После расшифровки записей выяснилось, что они повествуют об общественном
устройстве и культуре исчезнувшей цивилизации.
В частности, письмена сообщали о том, как во времена расцвета этой цивилизации было
организовано производство и распределение пищи.
Оказалось, что вокруг города
располагались поля с каким-то съедобным растением, отличавшимся крайне высокой
урожайностью. Осенью любой горожанин мог придти на любое такое поле и взять свою
долю плодов. Эта доля была строго фиксирована, причём доли любых
двух жителей города были равны. Никто не мог взять ни больше, ни меньше своей доли.
Если кто-то, приходя на поле, обнаруживал, что там осталось меньше
плодов, чем ему причитается, он ничего не брал и отправлялся на другое поле.
Оставшиеся плоды пускали на семена, в результате чего из каждого из них
на следующий год вырастало некоторое количество новых плодов. Это количество
было всегда одинаковым и не зависело ни от года, ни от того, из какого
плода были взяты семена.
Вы нашли рядом с тем местом, где когда-то находилось ближайшее к городу
поле, пронумерованные таблички с некоторыми числами. Вы предположили,
что на этих табличках вёлся ежегодный учёт плодов, оставшихся к началу зимы на этом
поле, и что плодов на поле всегда оставалось меньше,
чем размер одной доли. От года к году внешний вид табличек несколько менялся, и возможно, что
более новые из них имели совершенно иное назначение.
Определите наибольшее количество старых табличек, записи на которых не
противоречат вашему предположению.
Исходные данные
В первой строке записано целое число 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)