题面描述

一年一度的校园歌手大赛开始了，今年一共有 $n$ 个选手参与了比赛，分别编号为 $1\sim n$ ，每个人的唱功可以用数字 $a_i$ 来量化，保证 $a_1\sim a_n$ 互不相同。

今年赛事委员会决定让比赛变得更刺激一点，于是采用了以下的赛制：

• 编号为 $2d+1$ 的选手和编号为 $2d+2$ 的选手会通过对唱来PK（$d$ 为整数），唱功更高的选手（即 $a_i$ 更大的选手）获胜，晋级下一轮。如果 $n$ 为奇数，则编号为 $n$ 的选手轮空，直接晋级。这一轮所有淘汰的选手，其最终名次就是第 $\lceil\frac n2\rceil+1$ 名。
• 所有晋级的选手重新编号 $1\sim \lceil\frac n2\rceil$ ，继续下一轮。
• 直到剩下一个选手，Ta就是歌手大赛的冠军，其名次也就是第 $1$ 名。

唱功不错的小 B 却惨遭一轮游，原因是第一轮遇到的对手最后获得了冠军。

所以他为了向赛事委员会说明这个比赛规则的不合理性，他想对于每一个 $i$ ，求出如果初始编号为 $i$ 的选手能在第一次被淘汰的那一场比赛获胜晋级，他最终能得到什么名次。

输入格式

第 $1$ 行包含一个正整数 $n$，表示选手数量。

第 $2$ 行包含 $n$ 个正整数 $a_1,a_2,...,a_n$ 表示每一位选手的唱功。

输出格式

包含一行 $n$ 个整数，含义如题。

样例一

输入

10
3 9 6 12 15 24 30 18 27 21

输出

4 3 4 2 4 2 1 4 1 2

样例解释

第一轮选手 $[3,9,6,12,15,24,30,18,27,21]$

第二轮 $[9,12,24,30,27]$

第三轮 $[12,30,27]$

第四轮 $[30,27]$

第五轮 $[30]$

对于选手 $2$，他第一次被淘汰在第二轮，若获胜，则第三轮选手是 $[9,30,27]$，所以选手 $2$ 最后的名次变成了 $3$ 。

数据范围

对于所有数据 $n\le 5\times 10^5,a_i\le 10^9$ ，并且互不相同。

$\text{A}:$ 保证 $a_i$ 递增。