题目描述

薯条哥从一个神秘人那里获得了一个长度为$n$的数组。神秘人告诉薯条哥，薯条哥可以修改数组的一个元素，来改变数组的最小差异度。薯条哥想知道，当他修改第$i$个元素为多少时，数组的的最小差异度会最小？

数组的最小差异度定义为：数组所有相邻元素差值的绝对值的和。

输入描述

第一行为一个整数$n(2\le n \leq 10^5)$，代表数组的长度

第二行为$n$个正整数$a_i(1\le a_i\le 10^9)$，代表数组元素。

输出描述

$n$个整数，代表修改第$i$个元素能够达到的最小差异度。

样例

输入

4
1 2 1 2

输出

2 1 1 2