题目描述

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

输入格式

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

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

输出格式

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

3
2 3 4

1
1
1

样例1解释

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

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

数据范围

对于10%的数据，n≤1

对于30%的数据，n≤2

对于60%的数据，n≤100

对于80%的数据，n≤1000

对于100%的数据，n≤10^5，ai≤10^9

存在10%的数据，ai=1