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

内存限制:256 MiB 时间限制:2000 ms 输入文件:deflection.in 输出文件:deflection.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目背景

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

友情提示:题目名称是雪风随便起的,不代表题目实际内容。(这是真话)

题目描述

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

  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 的分数。

对于所有数据:

Subtask 数据范围 特殊性质 分数
1 n=50 10
2 n=300
3 n=5000 20
4 n=199991 序列 单调不减 10
5 n=199992 序列 单调不增
6 n=199993 序列 没有重复元素 20
7 n=200000