Cấp số cộng dài nhất

Cho dãy số nguyên dương \(A = (a_1, a_2, \dots, a_N)\). Một dãy con của \(A\) là dãy thu được bằng cách xoá đi một số phần tử (có thể không xoá) và giữ nguyên thứ tự các phần tử còn lại.

Một dãy con \(b_1, b_2, \dots, b_k\) được gọi là cấp số cộng công sai \(D\) nếu \(b_{t+1} - b_t = D\) với mọi \(1 \le t < k\). Dãy con chỉ có một phần tử luôn thoả mãn với mọi \(D\).

Bạn được tự do chọn một công sai nguyên \(D\) với \(1 \le D \le 50\). Hãy tìm độ dài lớn nhất của một dãy con của \(A\) là cấp số cộng với công sai \(D\) đã chọn.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\).

Output

• In ra một số nguyên duy nhất: độ dài lớn nhất tìm được.

Constraints

• \(1 \le N \le 10^5\)
• \(1 \le a_i \le 10^9\)

Sample Input

10
4 9 6 8 10 12 14 3 16 18

Sample Output

8

Explanation

Chọn \(D = 2\), dãy con \(4, 6, 8, 10, 12, 14, 16, 18\) gồm \(8\) phần tử là một cấp số cộng công sai \(2\). Không có cách nào dài hơn.