题目描述

小 $C$ 是个探险家，在金银岛上找到了许多宝藏，其中就有 $n$ 袋金币，每袋金币数量为 $a_i$ 。可是后来有坏人把其中几袋换成假币了，经过检查后发现每袋金币要么全是真币（每个重 $5$ 克），要么全是假币（每个重 $4$ 克）。

如果现在只有一台电子秤， $n$ 袋金币依次排列，你可以从每袋金币中挑出若干枚进行一次称量（也可以一枚都不选），若要确定前 $1$ , $2$ , ... , $n$ 袋金币的真假，至少要称量几次呢？

输入格式

第一行一个整数 $n$ ，表示有 $n$ 袋金币。

接下来一行 $n$ 个整数 $a_i$ ，表示每袋金币的数量。

数据范围

对于 10% 的数据，$n \le 1$

对于 30% 的数据，$n \le 2$

对于 60% 的数据，$n \le 100$

对于 80% 的数据，$n \le 1000$

对于 100% 的数据，$n \le 10^5 , a_i \le 10^9$

存在 10% 的数据，$a_i = 1$

输出格式

$n$ 行，每行一个整数，第 $i$ 行表示想要确定前 $i$ 袋金币的真假至少要称量几次。

样例

3
2 3 4

1
1
1

样例解释

以前三袋硬币为例，分别取出 1 、 2 、 4 枚硬币，则一次称量的结果即可确定三袋的真假。