AT_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 翻译