生成每个符号的码长

难度：T2

【知识点：前缀编码】【知识点：哈夫曼树】

前置知识：字符串、一维数组、循环、函数、树的路径

题目描述

给定各符号的正频数，构造确定的二元哈夫曼树，输出每个原符号的码长。原符号编号为 $1$ 到 $n$。每次在当前所有树根中，按权值从小到大、同权按编号从小到大，选前两个并合并。新父编号从 $n+1$ 开始依次递增，权值为两子树权值和。重复直到只剩一棵。码长是根到原叶经过的边数，按原符号编号输出，不按频数排序。

输入格式

第一行整数 $n$。第二行 $n$ 个整数 $w_i$，依次是编号 $i$ 的频数。

输出格式

输出一行 $n$ 个码长，按原符号编号顺序用空格分隔。

样例输入

4
8 4 2 1

样例输出

1 2 3 3

样例解释

合并权值为 $3,7,15$，各原叶深度为 $1,2,3,3$。

数据范围

$2\le n\le200$，$1\le w_i\le10^6$。