G. Reconstruction
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

After long research into an ancient cipher, you are sure that you are closer than ever to deciphering it.

However, to do this, you need to reconstruct an array $$$a$$$ of length $$$n$$$ that satisfies certain properties, or determine that no such array exists.

1) All elements of the array $$$a$$$ are distinct non-negative integers not exceeding $$$10^{18}$$$.

2) For each index $$$i$$$ from $$$1$$$ to $$$n$$$, you are given an index $$$j \ne i$$$ such that for any $$$k$$$ $$$(k \ne i, k \ne j)$$$, the following holds: $$$|a_k - a_i| \gt |a_i - a_j|$$$.

3) Among all arrays satisfying conditions $$$1$$$ and $$$2$$$, the array $$$a$$$ has the minimum possible value of its maximum element.

If there are multiple arrays satisfying conditions $$$1$$$, $$$2$$$, and $$$3$$$, you may output any of them.

Input

The first line of the input contains an integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$j_1, j_2, \ldots, j_n\, (1 \le j \le n)$$$ — the indices $$$j$$$ known to you for the corresponding $$$i$$$.

Output

If there exists at least one array satisfying conditions $$$1$$$, $$$2$$$, and $$$3$$$, output its elements $$$a_1, a_2, \ldots, a_n$$$ separated by spaces on a separate line.

Otherwise, output $$$-1$$$.

Examples
Input
5
4 1 5 1 3
Output
2 0 5 3 6
Input
4
2 3 4 2
Output
-1