Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

A. Autumn Audio
time limit per test
11 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Image by Albert Bridge, from commons.wikimedia.org

As autumn approaches, amazing audio appears. Few things are as satisfying as the crunch of a dry leaf underfoot, except the crunch of a leaf under a bicycle, which comes twice: once from the front wheel, and once from the back.

You are walking through Reykjavík, listening to a single e-bike crunch its way down an otherwise empty street. In Iceland, e-bikes ride at exactly $$$10$$$ metres per second, the fastest speed at which the police still pretend not to notice. So the bike covers exactly one centimetre every millisecond. You wonder whether the crunches alone reveal the bike's wheelbase: the distance between the points where its two wheels touch the ground (or, equivalently, between the centres of its wheels).

You hear every crunch, and every leaf is crunched exactly twice: first by the front wheel, and later by the back wheel. You keep an open mind about the bike's dimensions: even a wheelbase of one centimetre or of a hundred kilometres is fine by you.

For example, suppose you hear $$$4$$$ crunches, at milliseconds $$$100$$$, $$$200$$$, $$$300$$$ and $$$400$$$. There are two possible wheelbases.

The first possibility is that the wheelbase is $$$100$$$ centimetres and the two leaves are $$$200$$$ centimetres apart. Then the front wheel crunches the first leaf at $$$100$$$ and the back wheel crunches it at $$$200$$$; the front wheel crunches the second leaf at $$$300$$$ and the back wheel crunches it at $$$400$$$.

The second possibility is that the wheelbase is $$$200$$$ centimetres and the two leaves are $$$100$$$ centimetres apart. Then the front wheel crunches the first leaf at $$$100$$$ and the second leaf at $$$200$$$; the back wheel crunches the first leaf at $$$300$$$ and the second leaf at $$$400$$$.

Input

The input consists of:

  • One line with an even integer $$$n$$$ ($$$2 \leq n \leq 10\,000$$$), the number of crunches.
  • One line with $$$n$$$ integers $$$t_1, \dots, t_n$$$ ($$$1 \leq t_1 \leq \dots \leq t_n \leq 10^9$$$), the times of the crunches in milliseconds. Several crunches can happen at the same time; you hear each of them.
Output

Output the number of possible wheelbases, followed by the possible wheelbases in centimetres, in increasing order, one per line. In particular, if no wheelbase is consistent with the crunches, output a single line with $$$0$$$.

Examples
Input
4
1 2 3 4
Output
2
1
2
Input
6
1 1 2 2 3 3
Output
0
Input
6
1 3 5 7 11 15
Output
1
4