Background

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

Input

第一行一个整数$n$，表示硬币的堆数。

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

Output

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

Samples

3
2 3 4

1
1
1

Limitation

【样例1解释】

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

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

【数据范围】

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

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

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

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

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

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