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\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 $ を満たすものの個数を求めてください。

入力は以下の形式で与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $

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

### Sample Explanation 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 $ です。 ### Constraints - 入力はすべて整数 - $ 2\le N\le 3\times 10^5 $ - $ (P_1,P_2,\dots, P_N) $ は $ (1,2,\dots, N) $ の順列