정올학교 컴퓨터 시간에는 프로그래밍을 배운다. 따라서 컴퓨터 시간에 마우스보다는 키보드를 많이 쓰게 된다. 그런데 컴퓨터 선생님인 택쌤은 이상하게도, 키보드 소리인 다다다다닥…보다는 마우스 소리인 딸깍딸깍딸깍… 소리를 더 많이 듣고 있다. 학생들이 몰래 게임을 하고 있는 것이 분명했다.

 

택쌤은 모든 학생들의 컴퓨터에 몰래게임 감지기를 설치했다. 이는 다음과 같이 작동한다. 학생들 중 한명이라도 게임을 실행하면, 택쌤의 컴퓨터에 있는 카운터가 0으로 초기화된다. 매 분마다, 아무도 게임을 하지 않으면 카운터가 1, 2, 3…등으로 1씩 올라간다. 그러다가 다시 한명이라도 게임을 하면 카운터가 다시 0으로 바뀐다. 수업은 첫 번째 학생이 게임을 실행한 후 N분 동안 진행되므로, 총 N개의 카운터 기록이 남게 된다.

 

수업이 끝난 후, 택쌤이 화장실을 갔다 왔다. 택쌤은 학생들이 얼마나 게임을 많이 했나 보려고 카운터를 보았다. 웬걸, 숫자가 조작되어 있었다. 그래서 학생들이 얼마나 게임을 했는지 알 수가 없었다. 택쌤이 자명하게 아는 한 가지 사실은, 첫 번째 학생이 게임을 실행할 때부터 N분이 지났다는 것과, 처음 카운터가 0이었다는 것뿐이다. 택쌤은 게임 실행 횟수를 1, 2, 3,..N번으로 가정하고 학생들이 최소 몇 개의 숫자를 조작했나 궁금해졌다. 이를 구하는 프로그램을 작성하라. 두 명 이상의 학생이 같은 시간대에 게임을 하는 것도, 1번의 게임으로 가정한다.

 

첫 줄에 첫 학생이 게임을 시작한 후 수업이 끝날 때까지의 시간인 N이 주어진다.(1 <= N <= 100) 다음 줄에 N개의, 매 분마다 기록된 카운터들이 공백을 사이에 두고 주어진다. 이는 물론 조작 후의 카운터이다. 카운터는 0이상 100이하이다.

N개의 줄에 걸쳐서 다음을 출력한다: i번째 줄은 학생들이 게임을 i번 했을 때, 조작된 숫자의 최소 개수이다.

6
1 1 2 0 0 1

4
2
1
2
3
4

일단 첫번째 카운터가 1일 수가 없다(첫 학생이 게임을 시작하면 카운터는 0이다). 따라서 게임 수에 상관없이, 첫번째 카운터는 무조건 조작되었단 뜻이므로, 모든 경우의 답이 1 이상임이 자명하다. 첫 번째 줄: 게임을 한 학생이 1명뿐이라면, 카운터는 0 1 2 3 4 5여야 한다. 따라서 이 경우 1 1 2 0 0 1 중 맞는 게 두번째와 세번째 수인 1과 2밖에 없으므로, 4개의 숫자가 조작되었다는 뜻이다. 두 번째 줄: 게임을 한 학생이 2명이라면, 가능한 카운터 중 하나는 0 1 2 3 0 1이다(즉 카운터 작동 후 0-1분과 4-5분에 게임을 했다는 뜻이다.) 이 경우 1 1 2 0 0 1 중 맞는게 네 개 있으므로, 조작된 수는 두개이다. 두개보다 작아질 수는 없다. 세 번째 줄: 3명이 게임을 했다면, 최소 조작 수는 1개이며, 이 때의 가능한 카운터는 0 1 2 0 0 1이다.