Eric's Sequence

Given a sequence p of n non-negative integers, construct n pairwise distinct integers a. For any two indices i and j (i=j allowed), a[i]+a[j] must not equal 0; for each i, the number of indices j with a[i]+a[j]>0 must be exactly p[i], including j=i. Among all feasible constructions, minimize max(|a[i]|). Output any optimal construction; if there is no solution, output None. The original statement allows any optimal sequence; this site uses a semantic checker and does not require matching the examples or the reference construction.

输入格式

The first line contains n, 1≤n≤100000. The second line contains n non-negative decimal integers p[i]; leading zeros are allowed. The original gave no upper bound on p[i], and this site adds no numeric upper bound; inputs with p[i]>n naturally have no solution. Very long integers may also appear; read them as text to decide.

输出格式

If there is no solution, output None with exactly this capitalization; otherwise output n space-separated integers, corresponding to a[0] through a[n−1] in order, that achieve the minimum possible maximum absolute value. Do not output square brackets.

样例 1

输入：

1
0

输出：

-1

样例 2

输入：

1
1

输出：

1

样例 3

输入：

2
1 1

输出：

None

样例说明

For p=[0], [-1] can be output; for p=[1], [1] can be output, since its own positive-sum count is 1; p=[1,1] has no solution, because for two nonzero integers with different absolute values, the count of the one with the larger absolute value can only be 0 or 2.