A - Depth of Interval 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

正整数 N と (1,2,\dots ,N) の順列 P=(P_1,P_2,\dots ,P_N) が与えられます。

整数組 (L,R) に対して、f(L,R) を次のように再帰的に定めます。

  • 1\le L\lt 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 のそれぞれについて、整数組 (L,R) であって f(L,R)=k を満たすものの個数を求めてください。

制約

  • 入力はすべて整数
  • 2\le N\le 3\times 10^5
  • (P_1,P_2,\dots, P_N) は (1,2,\dots, N) の順列

入力

入力は以下の形式で与えられる。

N
P_1 P_2 \dots P_N

出力

N 行出力せよ。k=1,2,\dots, N について、k 行目には、整数組 (L,R) であって f(L,R)=k を満たすものの個数を出力せよ。


入力例 1

7
2 6 5 1 4 7 3

出力例 1

14
7
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 です。

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

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