题目描述

Samuel 最近成为遥远国度 Reyjrland（读作“Ragerland”）的第一任国王。作为国王必须完成的“就职准备杂务合集”的一部分，他需要确保各座城市能够展现自己的形象。

Reyjrland 可以表示为一个长度为 $n$ 的整数数组，其中每个整数对应国内一座城市的数值。对于长度至少为 $k$ 的数组 $b$，定义 $f(b,k)$ 为 $b$ 中第 $k$ 大的值。如果对于 $a$ 的所有长度至少为 $k$ 的连续子数组 $b$，$f(b,k)$ 都相同，就称这些城市“展现了第 $k$ 任国王的形象”。

当前城市数值组成的数组 $a$ 可能还无法展现国王的形象。为了修正它，国王每天可以选择一座城市，把该城市的数值增加 $1$ 或减少 $1$。

Samuel 曾经花费许多天低效地随机修改城市数值，直到数组能够展现自己的形象。他发誓绝不让未来的国王重蹈覆辙。因此，他要求你对从 $1$ 到 $n$ 的每个 $k$，分别求出把当前城市数值变成能够展现第 $k$ 任国王形象的数组所需的最少天数。

为某一任国王所作的修改不会延续到其他国王。也就是说，每任国王的统治结束后，城市数值都会重置为原数组 $a$ 中的值。

如果数组 $b$ 可以通过从数组 $a$ 的开头删除若干个元素（可以为零个或全部），并从末尾删除若干个元素（同样可以为零个或全部）得到，那么 $b$ 是 $a$ 的连续子数组。特别地，一个数组也是它自身的连续子数组。

输入格式

第一行包含一个整数 $n$（$1\le n\le2\cdot10^5$），表示城市数量，也就是数值数组的长度。

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

输出格式

输出 $n$ 行，每行一个整数。第 $k$ 行应为第 $k$ 任国王使数组展现其形象所需的最少天数。

3
2
3
1

2
1
0

4
1000000000
1
1000000000
1

1999999998
999999999
0
0