Cấp số cộng là một dãy số gồm ít nhất hai số và với mọi số trong dãy (trừ số đầu tiên) đều bằng số đứng kề trước nó cộng với một hằng số $d$ không đổi. Hằng số $d$ được gọi là công sai của cấp số cộng. Yêu cầu: Cho trước dãy gồm $n$ số nguyên dương $a_1, a_2, …, a_n$. Hãy tìm cách loại bỏ một số các số trong dãy (không thay đổi trật tự các số) để những số còn lại tạo thành một cấp số cộng có công sai $d$ là một số nguyên dương và có độ dài lớn nhất.

Dữ liệu vào

• Dòng đầu ghi số nguyên $n$ $(2 ≤ n ≤ 3000)$;
• Dòng thứ hai ghi dãy số gồm $n$ số nguyên dương $a_1, a_2, …, a_n$, mỗi số có giá trị không vượt quá $3000$ và giữa các số cách nhau một dấu cách.

Kết quả

Một số nguyên duy nhất là độ dài lớn nhất của dãy số tạo thành cấp số cộng tìm được theo yêu cầu bài toán.

Ràng buộc

• Có 40% số test với $n ≤ 100$.
• Có 60% số test với $100 < n ≤ 3000$

Ví dụ:

Input 1

7
1 4 5 6 8 2 10 

Output 1

4 

Input 2

`8 3 1 5 2 6 5 6 8

`

Output 2

3