Совсем недавно на одной из планет в системе Бетельгейзе были найдены руины древнего города. Особое внимание привлёк к себе неплохо сохранившийся храм, стены которого были исписаны многочисленными текстами. После расшифровки записей выяснилось, что они повествуют об общественном устройстве и культуре исчезнувшей цивилизации.

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

Вы нашли рядом с тем местом, где когда-то находилось ближайшее к городу поле, пронумерованные таблички с некоторыми числами. Вы предположили, что на этих табличках вёлся ежегодный учёт плодов, оставшихся к началу зимы на этом поле, и что плодов на поле всегда оставалось меньше, чем размер одной доли. От года к году внешний вид табличек несколько менялся, и возможно, что более новые из них имели совершенно иное назначение. Определите наибольшее количество старых табличек, записи на которых не противоречат вашему предположению.

В первой строке записано целое число n — количество табличек (1 ≤ n ≤ 10⁴). Во второй строке записаны целые числа a₀, a₁, …, a_{n − 1}, записанные на табличках (0 ≤ a_i ≤ 10⁹). На самой старой табличке записано число a₀, на самой новой — a_{n − 1}.

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