区间深度（Depth of Interval）

给定正整数 $N$ 和一个长度为 $N$ 的排列 $P=(P_1,P_2,\dots,P_N)$，其中 $P$ 是 $(1,2,\dots,N)$ 的一个排列。

对整数对 $(L,R)$，递归定义函数 $f(L,R)$：

• 若 $1\le L<R\le N$：在子数组 $P_L,P_{L+1},\dots,P_R$ 中，设最小值出现在位置 $a$（即元素为 $P_a$），次小值出现在位置 $b$（即元素为 $P_b$）。则$$f(L,R)=f(\min(a,b)+1,\ \max(a,b)-1)+1.$$
• 否则（即 $L\ge R$ 或不满足范围），定义 $f(L,R)=0$。

现在对每个 $k=1,2,\dots,N$，请你求出满足 $f(L,R)=k$ 的整数对 $(L,R)$ 的个数。

输入格式

输入格式如下：

N
P1 P2 ... PN

其中 $2\le N\le 3\times 10^5$，并且 $(P_1,\dots,P_N)$ 是 $(1,2,\dots,N)$ 的一个排列。

输出格式

输出 $N$ 行。第 $k$ 行输出满足 $f(L,R)=k$ 的整数对 $(L,R)$ 的个数。

样例

7
2 6 5 1 4 7 3

14
7
0
0
0
0
0

5
1 2 3 4 5

10
0
0
0
0

9
8 6 2 4 9 7 3 5 1

25
8
3
0
0
0
0
0
0

说明（对应样例 1）

样例 1 中，$f(1,7)$ 的计算过程为：区间 $[1,7]$ 的最小值在 $a=4$，次小值在 $b=1$，因此 $f(1,7)=f(2,3)+1$。接着区间 $[2,3]$ 的最小值在 $a=3$，次小值在 $b=2$，所以 $f(2,3)=f(3,2)+1$，而 $f(3,2)=0$，故 $f(1,7)=2$。