Azber's Tooth Marks

Interview

Time limit3sMemory limit1024 MB

Summary

Given sorted tooth mark positions, find every gap k where each mark has another mark exactly k away from it.

Level: Medium5 of 10
Topics: Array, Hash map, Brute force
Solved: No attempts yet

Problem

Food at home keeps disappearing, and you suspect your neighbor, the bear Azber. Today you finally found decisive evidence: tooth marks on a chocolate bar.

You think Azber bit the chocolate bar with two large canines and left several marks.

Treat the chocolate bar as a number line. Azber can leave tooth marks on the bar by following these rules.

At first, the bar has no marks.
When the gap between Azber's canines is $k$ ( $k > 0$ ), Azber can choose a number $x \ge 0$ and leave marks at positions $x$ and $x + k$ on the bar. Azber can repeat this action $0$ or more times.
If marks are left on the same position several times, only the last mark is visible.

You write down every possible canine gap $k$ based on the tooth marks on the bar, so you can check them when you meet Azber later.

Given the positions of the tooth marks, find every number that can be Azber's canine gap.

Input

The first line contains the number of tooth marks $N$ on the chocolate bar. ( $2 \le N \le 4\,000$ )

The second line contains the positions $x_1, x_2, \ldots, x_N$ of the tooth marks, separated by spaces, in ascending order. All $x_i$ are distinct. ( $0 \le x_i \le 10^9$ )

Output

On the first line, print the number $K$ of possible canine gaps for Azber.

If $K$ is at least $1$ , print the possible gaps on the second line, separated by spaces, in ascending order.

Examples3

Example 1
Input
```
4
0 5 10 15
```
Expected output
```
2
5 10
```
Example 2
Input
```
4
0 1 3 5
```
Expected output
```
0
```
Example 3
Input
```
2
5 28
```
Expected output
```
1
23
```