피보나치 동전

준혁이는 피보나치 동전을 화폐로 사용하는 피보나치 마을에서 살고 있다. $i$번째 피보나치 동전의 가치는$F\_i$ 이다.

$F\_i$는 피보나치 수열의 $i$번째 수를 의미한다. $F\_1 = 1, F\_2 = 1$ 이고, $i \geq 3$에서 $F\_i = F\_{i-1} + F\_{i-2}$로 정의된다.

준혁이의 $i$일차의 재산은 $M\_i$로 나타낸다. 준혁이는 $0$일차에 재산이 없으므로 $M\_0 = 0$이다. 준혁이는 $1$일차부터 $N$일차까지 $N$일간 정당한 노동을 하여 $i$일차에 일당으로 $A\_i$번째 피보나치 동전 $1$개를 받게 된다. 즉 $M\_i = M\_{i-1}+F\_{A\_i}$이다.

준혁이는 매일 밤, 자신의 재산을 최소 개수의 피보나치 동전으로 표현할 때 필요한 동전의 수를 알고 싶어한다. $1$일차 부터 $N$일차 까지, 재산 $M\_i$를 피보나치 동전들의 합으로 표현할 때 필요한 최소 동전 개수 $C\_i$를 구하여라.

첫째 줄에 $N$이 주어진다. $(1 \leq N \leq 250\\,000)$

둘째 줄에 $A\_1, A\_2, \cdots, A\_N$이 공백으로 구분되어 주어진다. $(1 \leq A\_i \leq 1\\,000\\,000)$

첫째 줄에 $C\_1, C\_2, \cdots, C\_N$을 공백으로 구분하여 출력한다.