Painting Points

Time limit2sMemory limit128 MB

Summary

Find a rotation angle and a red/blue coloring of circle points so rotated red points exactly match blue points, maximizing total painted points.

Level: Medium6 of 10
Topics: Math, Number theory, Greedy, Simulation
Solved: No attempts yet

Problem

Several points are placed on a circle at distinct integer angles. You want to paint some of these points red or blue.

The painted points must satisfy the following rule. There must be a rotation angle d such that rotating every red point by d degrees in the same direction makes the red points land exactly on the blue points. A point cannot be painted both colors.

Given the angles of the points on the circle, find the maximum number of points that can be painted while satisfying this rule.

Input

The first line contains the number of points N on the circle. (1 <= N <= 360)

Each of the next N lines contains the angle of one point. Every angle is an integer from 0 to 359, and no angle appears more than once.

Output

Print the maximum number of points that can be painted while satisfying the rule.

Examples4

Example 1
Input
```
7
0
10
15
25
40
50
60
```
Expected output
```
6
```
Example 2
Input
```
1
1
```
Expected output
```
0
```
Example 3
Input
```
8
0
1
3
7
15
31
63
127
```
Expected output
```
2
```
Example 4
Input
```
2
12
34
```
Expected output
```
2
```