CF1539F Strange Array

Vasya 有一个包含 $n$ 个整数的数组 $a_1, a_2, \ldots, a_n$。出于某种原因，Vasya 认为他数组中的所有数字都很奇怪。为了计算第 $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. 对于第一个位置，我们选择区间 $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$。 由 ChatGPT 4.1 翻译