시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Yuuka has a binary tree with vertices which are conveniently labeled with $1, 2, \dots, n$. For each $i \geq 2$, there is an edge between vertices $i$ and $\lfloor i / 2 \rfloor$. The $i$-th vertex has weight $w_i$ associated with it, and all weights are distinct.

Consider a subtree of the given tree (a subgraph which is itself a tree) which consists of vertices $v_1, v_2, \dots, v_k$ such that $w_{v_1} < w_{v_2} < \dots < w_{v_k}$. The $a$-median of this subtree is then $w_{v_{\lfloor (k - a + 1) / 2 \rfloor}}$ for $0 \leq a < k$.

For each $a \in \{0, 1, 2, \dots, n - 1\}$, find the largest $a$-median among all subtrees of the given tree.

입력

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

The first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$). 

The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \leq w_i \leq n$, and the numbers $w_1, w_2, \dots, w_n$ are all distinct). It is guaranteed that the sum of all $n$ does not exceed $2 \cdot 10^5$.

출력

For each test case, output $n$ integers $M_0, M_1, \dots, M_{n - 1}$ where $M_a$ denotes the largest $a$-median.

예제 입력 1

5
1 2 3 4 5
10
9 10 4 2 3 5 7 1 8 6

예제 출력 1

5 2 2 1 1
10 9 5 4 4 3 3 2 2 1