B. Almost AP
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

An array, is called an "Almost Arithmetic Progression" (Almost AP) if you can modify at most 3 elements in the array such that it becomes an arithmetic progression.

Recall the definition of the arithmetic progression: For an array a1, a2, ..., an to be an AP, ai + 1 - ai = c for all 1 ≤ i < n, in which c is a constant (c can be either positive, or negative, or 0).

You are asked to turn an Almost AP into an exact AP by modifying at most 3 numbers.

Input

The first line contains an integer n. (3 ≤ n ≤ 105)

The second line contains n space-separated integers: a1, a2, ..., an. ( - 109 ≤ ai ≤ 109)

Output

Output an arithmetic progression consisting of n integers b1, b2, ..., bn. Array b differs from array a by at most three numbers. You should also make sure that |bi| ≤ 1018.

The input guarantees there is at least one solution. If there are multiple of them, you can output any one.

Examples
Input
5
1 2 4 4 5
Output
1 2 3 4 5
Input
4
1 3 5 7
Output
1 3 5 7
Input
4
2 3 3 3
Output
4 3 2 1