AT_1_stpc2025_1_a.Depth of Interval

给定一个正整数 $N$ 和一个 $(1,2,\dots,N)$ 的一个排列 $P=(P_1,P_2,\dots,P_N)$。

对于整数对 $(L, R)$，递归地定义 $f(L,R)$ 如下：

• 当 $1\le L < R \le N$ 时，令 $a, b$ 为 $P_L,P_{L+1},\dots,P_R$ 中最小的和次小的数在排列中对应的位置，分别记为 $P_a, P_b$。定义 $f(L, R) = f(\min(a,b)+1, \max(a, b)-1) + 1$。
• 否则，定义 $f(L,R)=0$。

请你对于 $k=1,2,\dots,N$，分别计算所有满足 $f(L,R) = k$ 的整数对 $(L,R)$ 的个数。

输入为以下形式：

$N$ $P_1$ $P_2$ $\dots$ $P_N$

输出 $N$ 行。对于 $k=1,2,\dots,N$，第 $k$ 行输出所有满足 $f(L,R) = k$ 的整数对 $(L,R)$ 的个数。

样例解释 1

$f(1,7)$ 的计算如下。$P_1,P_2,\dots,P_7$ 中最小的和次小的数分别是 $P_4, P_1$。因此 $f(1,7) = f(2,3)+1$。

$f(2,3)$ 的计算如下。$P_2,P_3$ 中最小和次小的数分别是 $P_3, P_2$。因此 $f(2,3) = f(3,2)+1$。

$f(3,2)=0$，因此 $f(2,3)=1$。所以 $f(1,7)=2$。

数据范围

• 输入均为整数
• $2\le N\le 3\times 10^5$
• $(P_1,P_2,\dots, P_N)$ 是 $(1,2,\dots, N)$ 的一个排列。

由 ChatGPT 5 翻译