Hard to Miss

Matt is watching the shooting finals.

There are $n$ marksmen standing next to each other along the shooting range, numbered from $1$ to $n$ from left to right. A formation of $k$ targets moves across the range from left to right, with the same spacing as the marksmen. Hitting target $j$ adds $b_j$ points to a marksman's score.

Initially, target $j$ is directly in front of marksman $j$. Each second, every marksman with a target directly in front of them fires exactly once, and all shots are simultaneous. Every shot hits, and targets remain in the formation after being hit. If marksman $n$ has fired, the round ends; otherwise, the formation moves one position to the right before the next second.

Formally, let $c_i$ be the score of marksman $i$, initially $0$ for every $1 \le i \le n$. For each second $i = 1, 2, \ldots, n - k + 1$ in order, the following happens:

$c_{i + j - 1} \gets c_{i + j - 1} + b_j \quad \text{for every } 1 \le j \le k.$

Unfortunately, Matt is short-sighted and cannot see the targets. He can only see the final scoreboard $a_1, a_2, \ldots, a_n$, where $a_i$ is the score of marksman $i$.

Find a possible number of targets $k$ and their point values $b_1, b_2, \ldots, b_k$ that produce the given final scoreboard.

If there are several valid formations, output any of them. If none exists, output -1.

Input

The first line contains an integer $n$ ($1 \le n \le 2 \times 10^5$), the number of marksmen.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{18}$), their final scores.

Output

If no valid formation exists, print -1 on a single line.

Otherwise, print an integer $k$ ($1 \le k \le n$), the number of targets, on the first line. On the second line, print $k$ space-separated integers $b_1, b_2, \ldots, b_k$ ($1 \le b_j \le 10^{18}$), the targets' point values in their initial left-to-right order.

Example 1

3
2 5 3

2
2 3

Explanation

The formation has $k = 2$ targets, worth $2$ and $3$ points.

• Second $1$: marksman $1$ hits target $1$ for $2$ points, marksman $2$ hits target $2$ for $3$ points. The scoreboard reads $[2, 3, 0]$.
• Second $2$: the formation moves right by one position, so marksman $2$ hits target $1$ for $2$ points and marksman $3$ hits target $2$ for $3$ points. The scoreboard reads $[2, 5, 3]$. Since the rightmost marksman has hit a target, the round ends.

Example 2

5
2 7 10 8 3

4
2 5 5 3

Explanation

The formation has $k = 4$ targets, worth $2$, $5$, $5$ and $3$ points.

• Second $1$: the targets are in front of marksmen $1$ to $4$, and the scoreboard reads $[2, 5, 5, 3, 0]$.
• Second $2$: the formation has moved right by one position, so the targets are in front of marksmen $2$ to $5$. After they shoot, the scoreboard reads $[2, 7, 10, 8, 3]$. Since the rightmost marksman has hit a target, the round ends.

Another formation that is consistent with this scoreboard is $[2, 5, 3]$, which will also be accepted.

Example 3

1
7

1
7

Explanation

There is only one marksman, so the formation has one target and the round ends after one shot. The target must be worth exactly $7$ points.