You are given a sequence of n integers a_1, a_2, \dots, a_n. It is guaranteed that this sequence was originally an arithmetic progression, but exactly one element has been changed to a different integer value.
Your task is to identify the incorrect element and restore the original arithmetic progression. If there are multiple valid arithmetic progressions that can be formed by changing exactly one element, you may output any one of them.
Input
The first line contains a single integer n (3 \le n \le 2 \cdot 10^5), the number of elements in the sequence.
The second line contains n integers a_1, a_2, \dots, a_n (-10^9 \le a_i \le 10^9), representing the sequence with one incorrect value.
Output
Print n space-separated integers representing any valid original arithmetic progression that differs from the input by exactly one element.
Examples
| standard input | standard output |
|---|
| 4
1 3 9 7
| 1 3 5 7
|
| 5
10 4 6 8 10
| 2 4 6 8 10
|