progres

Gigel a progresat astăzi la matematică, și a învățat despre progresia aritmetică. Dacă avem primul element $a$ și o rație $r$, progresia aritmetică se formează astfel: $a, a + r, a + 2 \cdot r, \dots$

Cerință

Se dă un șir de $n$ numere, $a_1, a_2, \dots, a_n$. Să se afle lungimea maximă a unei subsecvențe $[l, r]$ a șirului $a$ unde $1 \leq l \leq r \leq n$, astfel încât există $k$ întreg, pentru care $a_i = a_l + k \cdot (i - l)$, pentru orice $i$ astfel încât $l \leq i \leq r$ (cu alte cuvinte, subsecvența de la $l$ la $r$ să fie progresie aritmetică).

Date de intrare

Pe prima linie a fișierului de intrare progres.in se găsește numărul întreg $n$. Pe următoarea linie se găsesc cele $n$ numere, $a_1, a_2, \dots, a_n$, separate prin câte un spațiu.

Date de ieșire

Pe prima linie a fișierului de ieșire progres.out se va găsi un singur număr întreg, lungimea maximă a unei secvențe de forma cerută.

Restricții și precizări

• $2 \leq n \leq 10 ^ 6$
• $1 \leq a_i \leq 10 ^ 9$, pentru $1 \leq i \leq n$.
• Pentru $20$ de puncte, $n \leq 10 \ 000$.

Exemplul 1

progres.in

10
1 2 3 4 2 7 12 17 22 27

progres.out

6

Explicație

Secvența $(2, 7, 12, 17, 22, 27)$ are lungime $6$ și este progresie aritmetică. Nu există subsecvențe de lungime mai mare ca $6$ și care să și respecte condițiile.

Exemplul 2

progres.in

5
1 2 3 4 5

progres.out

5

Explicație

Întregul șir este o progresie aritmetică!