A50149.稳定化子

夏绯在向威威学习高等代数。威威最近介绍了群作用相关的一些内容。轨道和稳定化子等概念令绯绯印象深刻且浮想联翩。

于是，她定义一个排列 $\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 \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$	A
9, 10	$2 \times 10^5$	B
11, 12	$2 \times 10^5$	C
13, 14	$2 \times 10^5$	D
15~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$