Problem Description

$\text{Mirka}$ is an amateur pianist, and she is learning a piece of music. However, she is not very good at finding the correct pitch, so she uses a special technique.

There are $N$ notes in the piece, and each note has a standard pitch $a_i$. $\text{Mirka}$ can play the first note accurately, and then she will choose a value $K$.

• If the standard pitch of the next note is greater than the standard pitch of the current note, she will increase the pitch she is currently playing by $K$.
• If the standard pitch of the next note is less than the standard pitch of the current note, she will decrease the pitch she is currently playing by $K$.
• If the standard pitch of the next note is equal to the standard pitch of the current note, she will not change the pitch she is currently playing.

If the pitch she is currently playing is equal to the standard pitch of the current note, then $\text{Mirka}$ has played a note correctly. Please help her find a non-negative integer $K$ so that she plays the maximum number of notes correctly.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $a_i$, where $a_i$ is the standard pitch of the $i$-th note.

Output Format

The first line outputs an integer, the maximum number of notes that $\text{Mirka}$ can play correctly.

The second line outputs a non-negative integer, the value of $K$. You only need to output any $K$ that satisfies the requirement.

5
1 2 0 3 1

3
2

7
2 1 -6 -2 1 6 10

5
4

Hint

[Sample 1 Explanation]

When $K=2$, the pitches she plays are 1, 3, 1, 3, 1. In total, she plays $3$ notes correctly.

Note that $K=1$ is also a feasible solution.

[Sample 2 Explanation]

When $K=4$, the pitches she plays are 2, -2, -6, -2, 2, 6, 10. In total, she plays $5$ notes correctly.

[Constraints]

For $100\%$ of the testdata, $2\le N\le 10^6$, $-10^9\le a_i\le 10^9$.

[Scoring Method]

This problem uses an unofficial self-written Special Judge, which can also be obtained from the attachments. Everyone is welcome to Hack (via private message or by posting). Hack testdata are placed separately at the end; the corresponding test points all have a score of 0.

[Source]

Translated from COCI 2015-2016 CONTEST #6 T3 PIANINO.

The score of this problem follows the original COCI setting, full score $100$.

Translated by ChatGPT 5