题目描述

斐波那契压缩是一种基于斐波那契数的容错压缩方式。一个合法码字不能在结尾以外的位置出现两个连续的 1，而码字末尾必须是两个连续的 1。

因此，对于任意码长 $i\ge2$，长度为 $i$ 的合法压缩码字共有 $F_{i-1}$ 个，其中 $F_1=F_2=1$ 为斐波那契数列。

最短的 14 个斐波那契码字如下：

11
011
0011 1011
00011 10011 01011
000011 100011 010011 001011 101011
0000011 1000011 ...

使用这种方式压缩一个字符串时，应把出现频率最高的字符替换为最短的码字，把次高频字符替换为次短的码字，以此类推，从而使压缩后的总长度尽可能小。

给定一个整数序列 $s$。对于它的每一个前缀，都单独进行一次最优斐波那契压缩。求每个前缀压缩后的最小长度。

注意：分别压缩每个前缀，与先压缩完整序列再删除末尾若干码字并不相同。

输入格式

• 第一行包含一个整数 $n$（$1\le n\le10^5$），表示序列长度。
• 第二行包含 $n$ 个整数 $s_1,s_2,\ldots,s_n$（$0\le s_i\le10^6$），表示待压缩的序列。

输出格式

输出 $n$ 个整数。第 $i$ 个整数表示前缀 $s_1,s_2,\ldots,s_i$ 在最优斐波那契压缩下的总码长，单位为比特。

这些整数可由空格或换行分隔。

样例 1

输入：
4
97 97 98 98

输出：
2 4 7 10

样例 2

输入：
24
1 75 2 1 1 75 75 75 75 75 75 2 2 3 4 5 6 7 8 9 10 11 12 10

输出：
2 5 9 11 13 16 19 21 23 25 27 31 35 39 44 49 54 60 66 72 78 84 91 95