Samuel 最近成为了遥远国度 Reyjrland（读作 “Ragerland”）的第一任国王。作为国王需要完成的“筹备工作首发合集”的一部分，他必须确保这些城市能够展现他的风采。

Reyjrland 可以用一个长度为 $n$ 的整数数组来表示，对应国家中 $n$ 个城市的值。如果我们定义 $f(b, k)$ 为长度至少为 $k$ 的数组 $b$ 中的第 $k$ 大值，那么如果对于 $a$ 的所有长度至少为 $k$ 的子数组$^\dagger$ $b$，$f(b, k)$ 都相同，则称这些城市展现了第 $k$ 代国王的风采。

城市当前的数值 $a$ 可能还无法展现国王的风采。为了解决这个问题，国王每天可以选择一个城市，并将其数值增加或减少 $1$。

在低效地随机修改城市数值、工作了许多天直到数组终于展现了他的风采之后，Samuel 发誓绝不让未来的国王经历同样的事情。他交给你一个任务：对于从 $1$ 到 $n$ 的所有 $k$，求出将当前城市数值转化为能够展现第 $k$ 代国王风采的数组所需的最少天数。为使数组展现第 $k$ 代国王风采而进行的修改不会保留到其他国王。也就是说，在每代国王的统治结束后，城市数值都会重置为原始数组 $a$ 中的值。

$\dagger$：数组 $b$ 是数组 $a$ 的子数组，如果 $b$ 可以通过从 $a$ 的开头删除若干个（可能是零个或全部）元素以及从末尾删除若干个（可能是零个或全部）元素而获得。特别地，一个数组是其自身的子数组。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示城市的数量，也是数值数组的长度。

接下来的 $n$ 行，每行包含一个整数。第 $i$ 行包含 $a_i$ ($0 \le a_i \le 10^9$)，表示第 $i$ 个城市的值。

输出格式

输出 $n$ 行，每行包含一个整数。第 $k$ 行应包含使数组展现第 $k$ 代国王风采所需的最少天数。

样例

输入样例 1

3
2
3
1

输出样例 1

2
1
0

输入样例 2

4
1000000000
1
1000000000
1

输出样例 2

1999999998
999999999
0
0