33984번 - 피보나치 동전

문제

준혁이는 피보나치 동전을 화폐로 사용하는 피보나치 마을에서 살고 있다. $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$을 공백으로 구분하여 출력한다.

제한

힌트