이진 트리에서의 중앙값

Yuuka에게는 정점이 $1, 2, \dots, n$으로 편리하게 번호가 매겨진 이진 트리가 있다. 각 $i \geq 2$에 대해 정점 $i$와 $\lfloor i / 2 \rfloor$ 사이에 간선이 있다. $i$번째 정점에는 가중치 $w_i$가 있으며, 모든 가중치는 서로 다르다.

주어진 트리의 부분 트리(그 자체가 트리인 부분 그래프) 중 정점 $v_1, v_2, \dots, v_k$로 이루어지고 $w_{v_1} < w_{v_2} < \dots < w_{v_k}$를 만족하는 것을 생각하자. 이 부분 트리의 $a$-중앙값은 $0 \leq a < k$에 대해 $w_{v_{\lfloor (k - a + 1) / 2 \rfloor}}$이다.

각 $a \in \{0, 1, 2, \dots, n - 1\}$에 대해, 주어진 트리의 모든 부분 트리 중에서 가장 큰 $a$-중앙값을 구하라.

입력은 0개 이상의 테스트 케이스로 이루어지며, 파일의 끝에서 종료된다. 각 테스트 케이스는 다음과 같다.

첫째 줄에 정수 $n$이 주어진다 ($1 \leq n \leq 2 \cdot 10^5$).

둘째 줄에 $n$개의 정수 $w_1, w_2, \dots, w_n$이 주어진다 ($1 \leq w_i \leq n$, 그리고 $w_1, w_2, \dots, w_n$은 모두 서로 다르다). 모든 $n$의 합은 $2 \cdot 10^5$을 넘지 않음이 보장된다.

각 테스트 케이스에 대해 $n$개의 정수 $M_0, M_1, \dots, M_{n - 1}$를 출력한다. 여기서 $M_a$는 가장 큰 $a$-중앙값을 나타낸다.