Vasya 有一个 $$$n$$$ 整数数组 $$$a_1, a_2, \ldots, a_n$$$。出于某种原因,瓦西亚认为他的数组中的所有数字都很奇怪。为了计算第 $$$i$$$ 个数字的奇怪程度,Vasya 创建了以下算法。
他选择一个子段$$$a_l, a_{l+1}, \ldots, a_r$$$,使得$$$1 \le l \le i \le r \le n$$$,在他的头脑中按升序对其元素进行排序(他可以任意排列相等的元素)。之后他找到了该线段的中心。如果段的长度是奇数,则段的中心是位置 $$$(l + r) / 2$$$ 处的元素,否则是位置 $$$(l + r + 1) / 2$$$ 处的元素。现在 Vasya 找到排序前位于 $$$i$$$ 位置的元素,并计算其当前位置与子段中心之间的距离(索引为 $$$j$$$ 和 $$$k$$$ 的元素之间的距离为 $$$|j - k|$$$)。
位置$$$i$$$处的数字的陌生度是$$$l$$$和$$$r$$$的所有合适选择中的最大距离。
Vasya 想要计算数组中每个数字的陌生度。帮助他做到这一点。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$) — 数组的大小。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — Vasya 的数组。
输出
打印一行包含 $$$n$$$ 数字。其中第 $$$i$$$ 必须等于数组中第 $$$i$$$ 元素的陌生度。
示例
输入 #1
5 5 4 3 2 1
输出 #1
2 1 1 2 2
输入 #2
7 3 6 5 6 2 1 3
输出 #2
2 3 1 3 2 3 1
注意
在第一个示例中:
1. 对于第一个位置,我们选择从 $$$1$$$ 到 $$$5$$$ 的段。排序后看起来是$$$[1,2,3,4,5]$$$,中心是$$$3$$$。从中心到$$$5$$$的距离是$$$2$$$。
2. 对于第二个位置,我们选择从 $$$2$$$ 到 $$$4$$$ 的段。
3. 对于第三个位置,我们选择从 $$$3$$$ 到 $$$5$$$ 的段。
4. 对于第四个位置,我们选择从 $$$1$$$ 到 $$$4$$$ 的段。排序后看起来是$$$[2,3,4,5]$$$,中心是$$$4$$$。从中心到$$$2$$$的距离是$$$2$$$。
5. 对于第五个位置,我们选择从 $$$1$$$ 到 $$$5$$$ 的段。