405218: GYM101848 B Almost AP
Description
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.
InputThe first line contains an integer n. (3 ≤ n ≤ 105)
The second line contains n space-separated integers: a1, a2, ..., an. ( - 109 ≤ ai ≤ 109)
OutputOutput 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.
ExamplesInput5Output
1 2 4 4 5
1 2 3 4 5Input
4Output
1 3 5 7
1 3 5 7Input
4Output
2 3 3 3
4 3 2 1