34939번 - 구슬 놀이 스페셜 저지

문제

길이 $N$의 수열 $A$가 있다고 하자. 구슬이 위치 $i$에 있을 때,

• $A_i > 0$이고 $i + A_i \le N$이라면 구슬은 위치 $i + A_i$로 이동한 뒤, $A_i$가 1ドル$ 감소한다.
• $A_i \le 0$ 또는 $i + A_i > N$이라면 구슬은 더이상 이동하지 않고 그 자리에서 멈추고, $A_i$가 1ドル$ 감소한다.

당신은 $N$개의 구슬을 위치 1ドル$에 하나씩 차례대로 놓으려고 한다. 구슬은 먼저 놓은 구슬이 멈춘 뒤에 다음 구슬을 놓는다. 각 구슬은 위치가 1ドル$로 시작해 어떤 구슬에서 멈춰 끝나게 되는 궤적을 이룰 것이다. 이 때 $k$번째에 떨어트린 구슬의 궤적의 길이, 즉 구슬이 방문한 위치의 개수를 $L_k$라 하자. ($L_k \ge 1$)

$N = 10^5$으로 주어질 때, 이 궤적의 길이의 합 $\displaystyle \sum_{k=1}^{N}{L_k}$가 29913857ドル$ 이상이 되게 하는 $A$를 출력하라.

입력

첫 번째 줄에 자연수 $N$이 주어진다. ($N = 10^5$)

출력

첫 번째 줄에 길이 $N$의 정수열 $A$를 공백으로 구분하여 출력한다. (0ドル \le A_i \le N$)

제한

노트