Multi-piano

Mirka is an amateur musician. She plays the multi-piano. The multi-piano has infinitely many keys, and every key carries an integer that gives its pitch. A larger integer means a higher pitch. A piece written for the multi-piano is a finite array of integers, and those integers list in order the keys a player presses.

Mirka heard a piece on the radio and wants to play it. She cannot tell which key was pressed. She only hears whether the key she just heard is higher than, lower than, or equal to the key before it. So she decided to play the piece this way:

• Before she starts, she picks one non-negative integer $K$.
• She presses the first key correctly. Her teacher told her which key that is.
• When the current key of the piece sounds higher than the previous one, she presses the key whose integer is $K$ larger than the key she pressed last.
• When the current key of the piece sounds lower than the previous one, she presses the key whose integer is $K$ smaller than the key she pressed last.
• When the current key of the piece sounds equal to the previous one, she presses the key she pressed last again.

While she plays, Mirka never compares the pitch she presses with the pitch of the piece. She keeps following the rule even after a wrong key.

Choose $K$ so that Mirka presses the correct key as many times as possible.

The first line contains the number of keys $N$ in the piece Mirka heard on the radio. ($2 \le N \le 10^6$)

The second line contains the keys $a_1, a_2, \dots, a_N$ pressed in the piece, separated by spaces. ($-10^9 \le a_i \le 10^9$)

On the first line, print the largest number of keys Mirka can press exactly as the piece does.

On the second line, print a non-negative integer $K$ that reaches that maximum. If several values of $K$ reach it, print the smallest one. The answer is always at most $2 \times 10^9$.