Migrated from Lutece 3014 空间扭曲之术

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在经历二向箔了打击的许多年之后，人类已经习惯了居住在二维世界中，并在这个世界里建立了新的秩序。 二维世界中现在还存活着 $n$ 个人类，第 $i$ 个人类生活在坐标 $(i,y_i)$ 。大家都知道两点之间的曼哈顿距离为 $|x_j-x_i|+|y_j-y_i|$ 。但是今天，由于某个公司的实验事故，空间发生了扭曲。曼哈顿距离的水平分量变成了 $\sqrt{|x_j-x_i|}$ ，垂直分量变成了$y_j-y_i$。即新曼哈顿距离的计算表达式为 $\sqrt{|x_j-x_i|}+y_j-y_i$ 。 面对突如其来的变故，人们惊慌失措。现在，人们迫切希望知道在新曼哈顿距离的定义下，离自己最远的人类（可以为自己本身）和自己之间的距离是多少（向上取整）。你能告诉他们吗？

Input

第一行一个整数 $n$ 第二行共有 $n$ 个整数，其中第 $i$ 个整数表示 $y_i$ 的大小

Output

输出一行 $n$ 个整数，其中第 $i$ 个整数代表在新曼哈顿距离的定义下，离第 $i$ 个人类最远的人类和他之间的距离（向上取整）。

Samples

6
5 3 2 4 2 4

2 3 5 3 5 4

Constraints

$1 \leq n \leq 100000$ $0 \leq y_i \leq 1000000$

Note

离自己最远的人类可以为自己本身

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming