← 返回比赛

已结束【提高组】GESP“飞翔杯”第三届季度赛

← 上一题下一题 →

A5029 | $稳定化子$

时间限制2s

内存限制1024MB

通过 / 提交0/0

题目描述

夏绯在向威威学习高等代数。威威最近介绍了群作用相关的一些内容。轨道和稳定化子等概念令绯绯印象深刻且浮想联翩。 于是，她定义一个排列 $\lbrace p_1, p_2, \dots, p_n \rbrace$ 的「稳定化子」为满足如下条件的位置对 $(x, y) \pod{1 \le x < y \le n}$：交换 $p_x, p_y$ 后，对于 $p$ 的任意子段 $\lbrace p_l, p_{l + 1}, \dots, p_r \rbrace$，其 $\mathrm{mex}$ 保持不变。（这里作如下定义：$\operatorname{mex} S = \min \lbrace x \in \mathbb Z_{\ge 1} : x \notin S \rbrace$。） 现在，她给了你一个具体的排列 $P = \lbrace p_1, p_2, \dots, p_n \rbrace$，并希望你可以求出：其各个位置分别在多少个稳定化子内部。

输入格式

第一行包含一个整数 $n$，表示 $P$ 的长度。 第二行包含 $n$ 个整数 $p_1, \dots, p_n$，表示 $P$。

输出格式

共一行 $n$ 个整数，第 $i$ 个整数表示 $p_i$ 出现在多少个稳定化子内部。

输入输出样例

输入 #1

3
2 3 1

输出 #1

0 0 0

输入 #2

5
1 3 5 2 4

输出 #2

0 1 1 0 0

输入 #3

7
4 1 7 6 3 2 5

输出 #3

0 0 2 2 2 0 0

对于所有数据，保证 $1 \le n \le 5 \times 10^5$，$\{p_i\}$ 为 $\{1, \dots, n\}$ 的排列。 测试点编号$n \le$特殊性质1$30$—2, 3$70$—4, 5$2 \times 10^2$—6, 7$2 \times 10^3$—8$2 \times 10^5$A9, 10$2 \times 10^5$B11, 12$2 \times 10^5$C13, 14$2 \times 10^5$D15~18$10^5$—19, 20$5 \times 10^5$— 特殊性质说明： - A：$p_i = i$ - B：$\{p_i\}$ 在 $\{1, \dots, n\}$ 的所有排列中均匀随机生成 - C：$p_1 p_n \le 5$ - D：$p_1 = 1$

C++ 编辑器

输入

输出