Description

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

Input Format

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

Output Format

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

3
2 3 4

1
1
1

Hint

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

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

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

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

【数据范围】
对于10%的数据，n≤1
对于30%的数据，n≤2
对于60%的数据，n≤100
对于80%的数据，n≤1000
对于100%的数据，n≤10^5，a_i≤Max_int

存在10%的数据，a_i=1

原题数据与描述不符，现修正100%数据范围为int最大值

Source

倍增 二进制