给你一个正整数 $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 ... P_N

数据范围

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

输出格式

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

样例

输入样例 1

7
2 6 5 1 4 7 3

输出样例 1

14
7
0
0
0
0
0

输入样例 2

5
1 2 3 4 5

输出样例 2

10
0
0
0
0

输入样例 3

9
8 6 2 4 9 7 3 5 1

输出样例 3

25
8
3
0
0
0
0
0
0

说明

在第一个样例中，值 $f(1, 7)$ 的计算过程如下。在 $P_1, P_2, \dots, P_7$ 中，最小的元素和第二小的元素分别为 $P_4$ 和 $P_1$。因此，$f(1, 7) = f(2, 3) + 1$。

接下来，在 $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$。