405218: GYM101848 B Almost AP

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 a₁, a₂, ..., a_n to be an AP, a_i + 1 - a_i = 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.

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

The second line contains n space-separated integers: a₁, a₂, ..., a_n. ( - 10⁹ ≤ a_i ≤ 10⁹)

Output an arithmetic progression consisting of n integers b₁, b₂, ..., b_n. Array b differs from array a by at most three numbers. You should also make sure that |b_i| ≤ 10¹⁸.

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

5
1 2 4 4 5

1 2 3 4 5

4
1 3 5 7

1 3 5 7

4
2 3 3 3

4 3 2 1