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

Input

3
2 5 3

Output

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

Input

5
2 7 10 8 3

Output

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

Input

1
7

Output

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.