시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB171825951.304%

문제

길이 $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$)

예제 입력 1

100000

예제 출력 1


						

예제 출력은 생략되었으나, 실제로는 첫 번째 줄에 답을 나타내는 $10^5$개의 정수를 공백으로 구분하여 출력해야 함에 주의하라.

채점 및 기타 정보

  • 예제는 채점하지 않는다.