Necklace

Peter bought a neklace with colored pearls to his sister- It is a magical necklace: the colors are changing at nights. The different colors are coded by positive numbers and if $c$ is the actual color of a pearl then its new color $c'$ is $$c' = \left\lfloor \frac{c_{-} + c + c_{+}}{3} \right\rfloor$$ where $c_{-},\ c_{+}$ are the colors of the two neighbouring pearls, and $\lfloor .\rfloor$ is the integer part function. The changes are happening at once! According to the seller, after some nights the colors will be the same. Peter wants to know this (final) color ($F$) and the number of nights needed to achieve this state ($T$). Help him to compute them!

Input specification

In the first line there is a number $M$, the number of pearls on the necklace. In the next line there are $M$ space separated numbers $c_i$, the actual colors of the pearls.

Output specification

In the first line the number nights $T$, then in the next one the final color $F$.

Constraints

$1\le N \le 10000$
$1\le c_{i} \le 10000$
$$\$$

Sample input 1

1. 3
2. 1 2 3

Sample output 1

1. 1
2. 2

Sample input 2

1. 6
2. 1 10 1 10 1 10

Sample output 2

1. 3
2. 5

Sample input 3

1. 9
2. 1 20 30 40 50 44 33 22 11

Sample output 3

1. 22
2. 21