题目描述

JOI 市有编号为 $1$ 到 $N$ 的 $N$ 名居民，居民 $i$（$1 \le i \le N$）的年龄为 $A_i$ 岁。

给定 JOI 市居民的年龄 $A_1, A_2, \dots, A_N$。请编写程序，对于每个 $i = 1, 2, \dots, N$，求出居民 $i$ 与其他居民之间年龄差的最大值。

约束条件

• $2 \le N \le 250000$。
• $0 \le A_i \le 10^9$（$1 \le i \le N$）。
• 输入的所有值均为整数。

子任务

1. （$25$ 分）$N = 2$。
2. （$30$ 分）$N \le 1000$。
3. （$45$ 分）无额外约束条件。

输入格式

输入以如下格式给出：

$N$ $A_1 \ A_2 \ \dots \ A_N$

输出格式

输出 $N$ 行。第 $i$ 行（$1 \le i \le N$）输出居民 $i$ 与其他居民之间年龄差的最大值。

样例

样例输入 1

3
13 15 20

样例输出 1

7
5
7

• 居民 $1$ 与居民 $2, 3$ 的年龄差分别为 $2, 7$ 岁。其中的最大值为 $7$ 岁，因此第 $1$ 行输出 $7$。
• 居民 $2$ 与居民 $1, 3$ 的年龄差分别为 $2, 5$ 岁。其中的最大值为 $5$ 岁，因此第 $2$ 行输出 $5$。
• 居民 $3$ 与居民 $1, 2$ 的年龄差分别为 $7, 5$ 岁。其中的最大值为 $7$ 岁，因此第 $3$ 行输出 $7$。

该样例输入满足子任务 $2, 3$ 的约束条件。

样例输入 2

2
100 100

样例输出 2

0
0

• 居民 $1$ 与居民 $2$ 的年龄差为 $0$ 岁。因此，第 $1$ 行输出 $0$。
• 居民 $2$ 与居民 $1$ 的年龄差为 $0$ 岁。因此，第 $2$ 行输出 $0$。

该样例输入满足所有子任务的约束条件。

样例输入 3

10
440894064 101089692 556439322 34369336 98417847 216265879 623843484 554560874 247445405 718003331

样例输出 3

406524728
616913639
522069986
683633995
619585484
501737452
589474148
520191538
470557926
683633995

该样例输入满足子任务 $2, 3$ 的约束条件。