April has a sequence of non-negative integers x1, x2, ..., xn.
She would like to make this sequence strictly increasing.
To do this, she can choose a non-negative integer k, and replace some of the xi with k - xi. In addition, after this replacement, all elements of the sequence must be non-negative.
Determine if there is some valid k that lets April get a strictly increasing sequence.
If there are multiple solutions, print any of them. If there are no solutions, print -1.
The output k must not exceed 2·109 + 1. It is guaranteed if a solution exists, there is a solution that doesn't exceed 2·109 + 1.
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000), the length of the sequence.
The next line contains n integers x1, x2, ..., xn (0 ≤ xi ≤ 109).
If there is no solution, print -1. Otherwise, on the first line, print a single non-negative integer k (0 ≤ k ≤ 2·109 + 1).
The next line contains n integers y1, y2, ..., yn (yi = xi or yi = k - xi, yi < yi + 1, 0 ≤ y0).
3
5 2 1
5
0 2 4
5
1 2 5 3 2
8
1 2 3 5 6
3
1 1 1
-1
