Workday Routine

Foreman Pavel leads a crew building a concert hall to a new design by foreign architects. The main feature is a colonnade at the main entrance with $n$ columns. Unlike classical designs, each column has its own height, not equal to the height of the roof above the entrance. In the current plan, the heights are $a_1, a_2, \ldots, a_n$ meters relative to the roof, from left to right. For example, height 10 means the column sticks out ten meters above the roof, and height -5 means there is a five meter gap between the top of the column and the roof.

Three days before the handover and opening, the architects arrived at the site and changed the design. The new requirement follows recent European fashion: the difference between any two adjacent columns must be the same. That is, for any integers $i$ and $j$ from 1 to $n - 1$, $a_{i+1} - a_i = a_{j+1} - a_j$ must hold. The exact height of each column does not matter. For technical reasons, each column height must be an integer number of meters relative to the roof.

Changing a column's height by $x$ meters, up or down, costs $x$ burles. Pavel asks you to choose a new height for each column so that the requirement holds and the total cost of the changes is as small as possible. Help him, or nobody will ever invite him to build foreign-designed buildings again.

The first line contains an integer $n$ ($2 \leq n \leq 3\,000\,000$), the number of columns in front of the building.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$), the current column heights.

Print two integers: the height of the first column and the difference between adjacent columns in an optimal plan.

The absolute values of both printed numbers must not exceed $10^{16}$. It is guaranteed that an optimal answer satisfying this exists.

In the first test, no changes are needed, since there are only two columns and they satisfy the requirement automatically.

In the second test, the optimal heights are 3, 7, 11, 15, 19, and the total cost is $|3 - 3| + |7 - 8| + |11 - 10| + |15 - 13| + |19 - 20| = 5$.