在史莱克居住的大沼泽周围，有 $n$ 只森林生物，它们住在环形排列的房屋中，使得第 $i$ 只生物和第 $i+1$ 只生物住在相邻的房屋，且第 $n$ 只生物也与第 $1$ 只生物相邻。每只生物都有一个它感到最舒适的首选沼泽温度 $t_i$。有一天，史莱克决定让所有生物都拥有相同的首选温度，从而体验到同样的舒适感。

每天晚上，史莱克都会邀请一些生物参加会议。在会议期间，会选择一组连续三间房屋的生物，其中一只生物可以将它的首选温度更改为这三者中最小或最大的首选温度。

对于每只生物，请确定史莱克使所有生物的首选温度都等于该生物初始首选温度所需的最少夜晚数。

输入包含 $n$ 个整数 $t_i$ —— 按照顺时针方向围绕沼泽给出的生物首选温度。

输入格式

第一行包含一个整数 $n$ —— 森林生物的数量。

第二行包含 $n$ 个整数 $t_i$ —— 生物的首选温度。

数据范围

$3 \le n \le 10^5$ $1 \le t_i \le 10^5$

输出格式

在一行中打印 $n$ 个用空格分隔的数字。第 $i$ 个数字表示使所有首选温度等于 $t_i$ 所需的最少夜晚数。

样例

输入 1

6
4 7 47 4 77 47

输出 1

4 6 4 4 5 4

说明

下图展示了每个晚上的会议，其中有三只生物聚集在一起。最终，所有生物的首选温度都变成了 4 度。

图 1: 第一晚

图 2: 第二晚

图 3: 第三晚

图 4: 第四晚