19397번 - Median on Binary Tree 다국어

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.