有 $n$ 堆硬币依次排列，第 $i$ 堆硬币有 $a_i$ 个。每堆硬币全是真币或全是假币，真币每个重 $5$ 克，假币每个重 $4$ 克。
你有一台电子天平，可以从每堆硬币中挑出若干个进行一次称量（也可以一个都不选）。现在你想要知道，若要确定前 $1,\ 2,\ \cdots,\ n$ 堆硬币的真假，至少要称量几次。

第一行一个整数 $n$，表示硬币的堆数。
接下来一行 $n$ 个整数 $a_i$，表示每堆硬币的数量。

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

对于 $10\%$ 的数据，$n≤1$；
对于 $30\%$ 的数据，$n≤2$；
对于 $60\%$ 的数据，$n≤100$；
对于 $80\%$ 的数据，$n≤1000$；
对于 $100\%$ 的数据，$n≤10^,\ a_i≤10^9$。
存在 $10\%$ 的数据，$a_i=1$。

1
1
1

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

重量	第一堆	第二堆	第三堆
28	假	假	假
29	真	假	假
30	假	真	假
31	真	真	假
32	假	假	真
33	真	假	真
34	假	真	真
35	真	真	真

但是各取出1枚硬币，是无法确定真假的。

重量	第一堆	第二堆	第三堆
12	假	假	假
13	真	假	假
13	假	真	假
13	真	真	假
14	假	假	真
14	真	假	真
14	假	真	真
15	真	真	真