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.

The first line contains an integer n that is an amount of tablets (1 ≤ n ≤ 10⁴). The second line contains integers a₀, a₁, …, a_{n − 1}, written on the tablets (0 ≤ a_i ≤ 10⁹). a₀ is written on the oldest tablet, a_{n − 1} is written on the newest one.

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 · 10¹⁸; 0 ≤ k ≤ 2 · 10¹⁸ (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.