Description

小 E 和小 F 正在玩一个游戏。

每轮游戏的流程是这样的：游戏开始时，小 F 会随机生成一个长度为 $n$ 的整数序列 $A_1 \sim A_n$，这个序列一共有 $\frac{n(n+1)}{2}$ 个不同的子区间。接着小 F 会随机选取一个子区间 $[l_1,r_1]$，然后小 E 会在剩下的子区间中再随机选取一个子区间 $[l_2,r_2]$。

此时，若序列 $A$ 中 $A_{l_1} \sim A_{r_1}$ 之和与 $A_{l_2} \sim A_{r_2}$ 之和相等，那么小 E 获胜，否则小 F 获胜。

在这次的游戏中，小 E 敏锐地观察到：$A$ 中似乎并不存在两个元素之和相等的子区间，所以自己根本不可能赢！于是，为了让游戏更加公平，小 E 决定小开一手。

具体来说，小 E 将会做若干次操作，每次操作选择一个 $A_i$，并令 $A_i \gets A_i + 1$ 或 $A_i \gets A_i-1$。为了让操作更难被小 F 察觉，小 E 希望自己每次操作选择的 $A_i$ 相同，且操作的总次数最小。

小 E 将这个问题交给了你。请你对于每个 $1 \leq i \leq n$ 求出：若小 E 选择对 $A_i$ 进行操作，使他可能获胜的最小操作次数。

Format

Input

第一行一个正整数 $n$，表示序列的长度。

第二行 $n$ 个整数 $A_1,A_2,\cdots,A_n$，描述小 F 生成的序列。

Output

一行 $n$ 个整数，第 $i$ 个整数表示若小 E 选择对 $A_i$ 进行操作，所需的最小操作数。整数之间用一个空格隔开。

Samples

3
3 -10 4

1 6 1

见附件中的 game/game2.in。

见附件中的 game/game2.ans。

见附件中的 game/game3.in。

见附件中的 game/game3.ans。

Limitation

【样例解释 #1】

对 $A_1$ 做 $1$ 次 $+1$ 操作，此时 $A_1 \sim A_1$ 之和与 $A_3 \sim A_3$ 之和相等。

对 $A_2$ 做 $6$ 次 $+1$ 操作，此时 $A_1 \sim A_1$ 之和与 $A_1 \sim A_3$ 之和相等。

对 $A_3$ 做 $1$ 次 $-1$ 操作，此时 $A_1 \sim A_1$ 之和与 $A_3 \sim A_3$ 之和相等。

【样例解释 #2】

该样例满足测试点 $6 \sim 8$ 的条件限制。

【样例解释 #3】

该样例满足测试点 $17 \sim 20$ 的条件限制。

【数据范围】

对于所有数据，保证 $1 \leq n \leq 10^3$，$-10^{18} \leq A_i \leq 10^{18}$。

温馨提示：请注意常数因子带来的程序效率上的影响。