#533. 「多校联考 2022 Round 3」序偏

题目背景

对社会的有机主体进行有序化重排后，总是会使一些主体离开它原有的位置。我们都知道，一个人待在他经常所在的位置上，是“舒适”的；如果让他离开这个位置，他就会感到不满。但为了社会整体的利益，我们必须要作这样的有序化重排，现在我们需要计算可能的不满意度。

友情提示：题目名称是雪风随便起的，不代表题目实际内容。（这是真话）

题目描述

给定一个长度为 的正整数序列 ，和它的所有元素 ，对于一个元素 ，我们定义它的最大可能不满意度 为：

1. 对一个元素 ，定义“重排”为：选定一段 内的区间 （），将 内所有元素按照从小到大的顺序排列，相同大小的元素之间可以任意放置。

2. 记 “重排”后的位置为 ，定义区间 的“中心”为 ，则 就等于所有合法的“重排”操作中 的最大值。

现在要求你求出所有的 。

从 deflection.in 中读入。

第一行一个正整数 。

第二行 个正整数，第 个为 。

输出到 deflection.out 中。

一行 个正整数，第 个为 。

样例输入 #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

样例 3~7

见附加文件，数据特性与编号对应的 Subtask 一致。

样例解释

对于样例 1：

1. 对于 ，我们选择区间 ，“重排”后序列 变为 ，序列的“中心”是位置 ， 现在到“中心”的距离为 。

2. 对于 ，我们选择区间 。

3. 对于 ，我们选择区间 。

4. 对于 ，我们选择区间 。

5. 对于 ，我们选择区间 。

因为随机数据的不可靠性，本题目采用 Subtask 制度进行评测，你必须通过一个 Subtask 中的全部数据才能得到这个 Subtask 的分数。

对于所有数据：

，