Yuuka 有一棵二叉树，其顶点编号为 $1, 2, \dots, n$。对于每个 $i \ge 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}$。对于 $0 \le a < k$，该子树的 $a$-中位数定义为 $w_{v_{\lfloor (k-a+1)/2 \rfloor}}$。

对于每个 $a \in \{0, 1, 2, \dots, n - 1\}$，求出所有子树中最大的 $a$-中位数。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 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$-中位数。

样例

样例输入 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