막대기

프로그램 명: stic

제한시간: 1 초

길이 N (1<=N<=200,000, N은 자연수) 인 막대기가 하나 있다.

당신은 이 막대기를 여러 조각으로 자르려고 한다. 물론 잘라진 막대기도 길이가 자연수여야 한다. 또한, 잘라진 막대기에서 몇개를 골라 연결하면 길이가 1-N 까지 모두 되게 하고싶다.

예를 들어서 N = 5 고 막대기를 길이 {1,1,3} 으로 자르면 연결했을때 길이를 1-N까지 만들수 있다.

하지만 막대기를 자르는 일은 너무 힘든 일이기때문에 자르는 횟수를 최소화하고 싶다.

입력은 없다.

i 번째 줄에 길이가 i인 막대기를 위 조건을 만족하면서 자르고 싶을때 그 최소 횟수 200,000 줄을 출력한다

처음 세줄만 예로 주어진다

입력

출력

0
1
1
...

출처:XXIV Colombian Programming Contest ACIS REDIS 2010 - ACM ICPC 
번역:likepad