Mirror Sort is an unconventional sorting algorithm which doesn't really sort an array. Rather, it performs a TЯOƧ to unorganize an array once more.

We begin with a sorted array of the integers ~1~ to ~N~, and the goal of the Mirror Sort algorithm is to convert this array into another given array, ~a_1, a_2, \dots, a_N~ with a sequence of reflections, ~x_1, x_2, \dots, x_M~.

A reflection about a non-negative integer ~x~ first decreases all elements in the array by ~x~, then flips the sign of any resulting negative numbers to be positive. In other words, a reflection about the non-negative integer ~x~ updates every value ~v~ to ~|v - x|~.

Can you find any sequence of ~M~ reflections, ~x_1, x_2, \dots, x_M~, which transforms the sorted array of integers ~1~ to ~N~ into the given array, ~a_1, a_2, \dots, a_N~? If no such sequence exists, output -1 instead.

For full points, ~M~ must be less than or equal to ~N~. You will receive 50% of the marks for a solution which satisfies ~M \le 3N~.

Constraints

~1 \le N \le 10^6~
~0 \le a_i\le 10^9~

Subtask 1 [80%]

~1 \le N \le 1000~

Subtask 2 [20%]

No additional constraints.

Input Specification

The first line contains one integer, ~N~, the length of the array.

The next line contains ~N~ space-separated integers, ~a_1, a_2, \dots, a_N~, the target array.

Output Specification

If it is impossible to convert the sorted array of integers ~1~ to ~N~ into the target array with a sequence of reflections, output -1 on one line.

Otherwise, output one integer, ~M~, the number of reflections in your solution.

Then, on the next line, output ~M~ integers in the inclusive range ~[0,10^{18}]~ separated by spaces, ~x_1, x_2, \dots, x_M~, the sequence of reflections. If ~M = 0~, this line should be empty.

Scoring

If it is impossible to convert the sorted array of integers ~1~ to ~N~ into the target array with a sequence of reflections, you will receive an Accepted verdict with full marks if you output -1 on one line. Otherwise, you will receive a Wrong Answer verdict.

If it is possible to convert the sorted array of integers ~1~ to ~N~ into the target array with a sequence of reflections, scoring will be done as follows:

If your outputted sequence of reflections does not convert the sorted array of integers ~1~ to ~N~ into the target array or is formatted incorrectly, you will receive a Wrong Answer verdict.

If your outputted sequence of reflections correctly converts the sorted array of integers ~1~ to ~N~ into the target array, your score will be determined by ~M~:

If ~M > 3N~, you will receive a Wrong Answer verdict.

If ~N < M \le 3N~, you will receive an Accepted verdict with 50% of the marks.

If ~0 \le M \le N~, you will receive an Accepted verdict with full marks.

Your score for a subtask will be the minimum score over all testcases within the subtask.

Sample Input 1

5
2 3 2 1 0

Sample Output 1

2
2 3

Explanation for Sample 1

We begin with the array ~[1,2,3,4,5]~.

After performing a reflection about the value ~2~, the resulting array is ~[1,0,1,2,3]~.

Finally, performing a reflection about the value ~3~ results in ~[2,3,2,1,0]~, which is the desired target array.

Since we have found a valid sequence of ~2~ reflections, and ~2 \le N = 5~, this sample output will receive full points.

Sample Input 2

2
1 1

Sample Output 2

-1

Explanation for Sample 2

It can be shown that it is not possible to convert the array ~[1,2]~ into the target array ~[1,1]~ with a sequence of reflections.