Mirka's Piano Tuning

Problem Statement

Mirka is an amateur pianist learning a new piece. However, she finds it challenging to hit the exact pitch. To cope with this, she uses a special technique when playing.

The piece consists of \(N\) notes. Each note has a standard pitch represented by \(a_i\) for \(i=1,2,\ldots,N\). Mirka can play the first note exactly. After playing the first note, she chooses a non-negative integer \(K\). For each subsequent note, she adjusts the pitch based on the comparison between consecutive standard pitches:

• If the next note's standard pitch is greater than the current note's standard pitch, she raises the pitch she just played by \(K\). That is, if the current played note is \(p\), then the next played note becomes \(p+K\).
• If the next note's standard pitch is lower than the current note's standard pitch, she lowers the pitch she just played by \(K\), making it \(p-K\).
• If the next note's standard pitch is equal to the current note's, she does not change the pitch.

A note is considered to be played correctly if the played note equals its standard pitch. Mirka wants to choose \(K\) so that the total number of correctly played notes is maximized. Your task is to find the maximum number of correctly played notes that can be achieved by an optimal choice of \(K\).

Note: The formulas above are provided in LaTeX format.

inputFormat

The input consists of two lines:

The first line contains an integer (N) (the number of notes). The second line contains (N) integers: (a_1, a_2, \ldots, a_N), representing the standard pitches of the notes.

outputFormat

Output a single integer: the maximum number of notes that Mirka can play correctly using an optimal non-negative integer (K).

sample

5
1 2 3 2 1

5