405218: GYM101848 B Almost AP

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Almost APtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard 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.

ExamplesInput
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

加入题单

上一题 下一题 算法标签: