H. Berland Prospect
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Bertown mayor had been receiving different complaints about insufficient lighting of the Berland Prospect — the main street of the city — for quite a while, and recently $$$n$$$ lanterns have been installed on the Prospect.

The Prospect can be represented as a segment of the coordinate line with endpoints in $$$0$$$ and $$$10^{18}$$$. Lanterns are installed in integer points of this segment; $$$i$$$-th lantern is installed in point $$$x_i$$$.

A large student festival will be held soon in Bertown, the students from all Berland are going to attend it. The mayor wants to impress them with the look of the Prospect during the night. To do so, the lighting system will be changed for only one night: some lanterns will be turned on, and all other lanterns will be turned off, so that the Prospect looks beautiful.

The mayor thinks that the Prospect will look beautiful if the following condition is met. Let's denote the indices of the lanterns that are turned on as $$$i_1$$$, $$$i_2$$$, ..., $$$i_k$$$ (in increasing order of coordinates), then the condition $$$x_{i_2} - x_{i_1} = x_{i_3} - x_{i_2} = \dots = x_{i_k} - x_{i_{k - 1}}$$$ should hold (that is, the distance between every two neighbouring working lanterns is the same). If the number of lanterns that are turned on is less than $$$3$$$, then the Prospect will look beautiful no matter where these lanterns are situated.

Of course, the better the lighting, the safer the Prospect will be. So the mayor wants to choose a set of lanterns to turn on of maximum possible size (among all sets such that the Prospect looks beautiful if all lanterns from the set are turned on). Help him to choose this set of lanterns!

Input

The first line contains one integer $$$n$$$ ($$$3 \le n \le 3\,000$$$) — the number of lanterns.

The second line contains $$$n$$$ integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ ($$$0 \le x_1 \lt x_2 \lt \dots \lt x_n \le 10^{18}$$$) — the coordinates of the lanterns.

Output

Print one integer — the maximum number of lanterns that can be turned on so that the Prospect looks beautiful.

Examples
Input
3
1 2 3
Output
3
Input
5
1 2 4 6 7
Output
3
Input
10
5 10 15 20 35 60 80 85 110 120
Output
5
Note

In the first example it is possible to turn all the lanterns on.

In the second example it is possible to turn the lanterns having coordinates $$$1$$$, $$$4$$$, $$$7$$$ on.

In the second example it is possible to turn the lanterns having coordinates $$$10$$$, $$$35$$$, $$$60$$$, $$$85$$$, $$$110$$$ on.