ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2012

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. The Lost Civilization

Time limit: 1.0 second
Memory limit: 64 MB
Recently, the ruins of the ancient city have been found on one of the planets in the system of Betelgeuse. Particular attention was drawn to the well-preserved temple with walls covered with numerous texts. Transcription revealed that they tell about the social structure and the culture of the lost civilization.
In particular, the lettering described how the production and distribution of food was organized in the heyday of this civilization. It was found that around the city there were fields with some edible plants characterized by extremely high yield. In the autumn any citizen could come to any such field and take its share of the fruits. This share was strictly fixed, and the shares of any two residents were equal. One could take no more and no less than his share was. If someone came to the field and saw that there were less fruits than he needed, he took nothing and went to another field. The remaining fruits were let to seeds, so from each of them some new fruits would grow next year. This number was always the same and did not depend on the year or which fruit the seeds were collected from.
You found tablets with some numbers at the place where the field nearest to the city once was. Perhaps an annual account of the fruit remaining at the beginning of winter in this field was carried out on these tablets. You also suggested that by this time of the year the quantity of fruit in the field was always less than the size of one share. The appearance of several tablets changed over years, and it is possible that more recent ones had a completely different purpose. Find the size of the share per capita and growth rate (how many fruits grew from seeds from one piece of fruit) that is consistent with as much of the oldest tablets as possible.

Input

The first line contains an integer n that is an amount of tablets (1 ≤ n ≤ 104). The second line contains integers a0, a1, …, an − 1, written on the tablets (0 ≤ ai ≤ 109). a0 is written on the oldest tablet, an − 1 is written on the newest one.

Output

Output integers L, P and k, meaning that integers on the first L tablets don’t contradict the size of the share P and growth rate k. Integers P and k must meet the following restrictions: 1 ≤ P ≤ 2 · 1018; 0 ≤ k ≤ 2 · 1018 (it is guaranteed that among the solutions of the problem there is at least one satisfying these constraints). If there are several solutions with maximum value L, output any of them.

Samples

inputoutput
5
1 2 4 8 0
5 16 2
3
4 2 1
3 5 3
Problem Author: Denis Dublennykh
Problem Source: Ural Championship 2012
To submit the solution for this problem go to the Problem set: 1906. The Lost Civilization