Acka Rhythm World

Time limit2sMemory limit512 MB

Summary

Given N distinct tap times, find the maximum count of times sharing the same remainder modulo some integer k >= 2, over all k and remainders.

Level: Medium7 of 10
Topics: Number theory, Math, Brute force, Implementation
Solved: No attempts yet

Problem

There is a new rhythm game called Acka Rhythm World. The score depends only on the times at which the screen was tapped.

After collecting $N$ tap times, for every integer $k$ with $k \ge 2$ and every integer $l$ , define $f(k, l)$ as the number of tap times that can be written in the form $ck + l$ , where $c$ is an integer. In other words, $f(k, l)$ counts the tap times whose remainder modulo $k$ equals the remainder of $l$ .

The score is the largest value of $f(k, l)$ over all choices of $k$ and $l$ .

Given the tap times, write a program that computes the score.

Input

The first line contains the number of taps $N$ ( $1 \le N \le 1000$ ).

The second line contains $N$ tap times in strictly increasing order, separated by spaces. All times are distinct integers from $0$ to $2000000$ inclusive.

Output

Print the score obtained by applying the rule to the given tap times.

Hint

Changing the integer $l$ is the same as choosing a remainder modulo $k$ . It never hurts to choose $l$ equal to one of the tap times. When $k$ is larger than every difference between tap times, distinct times fall into distinct remainders, so the score is $1$ .

Examples3

Example 1
Input
```
3
3 6 9
```
Expected output
```
3
```
Example 2
Input
```
5
1 2 3 6 7
```
Expected output
```
3
```

Example 3

Input

10
1 5 10 50 100 500 1000 5000 9999 10000

Expected output