Informatica Online Judge

  농장 탈출(Gold) [2185 / 0889]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 8   Total Tried : 14


The Champion of this Problem (C++) : gs17003 - 0ms / 1026byte
My Best Submission (C++) : N/A

[USACO 2018(Brian Dean & Dhruv Rohatgi)]

Background

농부 존은 이른 아침, 나무 울타리가 부서지는 소리에 일어났다. 범인은 젖소들이었다. 젖소들이 농장에서 또 탈출했다.

농부 존은 아프기도하고, 이른 아침에 젖소들이 탈출하는 것에 지쳤기 때문에 더 이상 두고 볼 수가 없었다.: 그래서 마음을 독하게 먹기로 했다.

존은 헛간 벽에, 이전 탈출 이후에 흐른 날짜를 추적할 수 있는 카운터를 설치했다. 오늘 아침에 탈출했으면 카운터는 0이 된다.;
마지막으로 3일 전에 탈출했었다면, 카운터에는 3으로 표시될 것이다. 농부 존은 카운터 기록을 매일 매일 꼼꼼히 기록했다.

연말이 다가와서, 농부 존은 그동안의 기록들을 정리할 준비를 했다. 농부 존은 젖소들을 처벌할 것이라고 이야기했다!
그런데, 카운터 기록이 왠지 정확하지 않은 것 같다....

농부 존은 카운터 기록을 시작한 이후로 얼마나 많이 탈출했는지 알아내려고한다.
하지만, 젖소들이 카운터 기록을 위조한 것 같다고 의심하고 있으며, 확실한 것은 탈출을 시작한 날부터 탈출을 기록하기 시작했다는 것이다.

탈출기록을 작성하기 시작한 이후로, 몇 번의 탈출이 있었는지 정확히 파악하기 위해서, 조작된 것이 틀림없는 최소 횟수를 알아내보자.

Input

첫 번째 줄에는 농부 존이 카운터 기록을 시작한 후 지난 일 수(N)가 입력된다.

두 번째 줄에는 N개의 정수가 공백을 두고 입력된다. i번째 정수 $a_i$(최대 100)는 i번째 날의 카운터 값을 의미한다.
젓소들이 그날 카운터를 조작하지 않았다면...

[입력값의 정의역]

$1≤N≤100$
$0≤a_i≤100$

Output

$N$줄에 걸쳐 N개의 정수를 출력한다. $i$번째 줄에는 $i$번 탈출했다고 가정했을 때, 기록을 조작했을 것으로 추정할 수 있는 최소 개수를 출력한다.

IO Example

입력
6
1 1 2 0 0 1

출력
4
2
1
2
3
4


* 설명 :
한 번만 탈출했었다면, 0 1 2 3 4 5로 기록되어야 하지만 1 1 2 0 0 1 이므로 최소 4개의 기록이 조작된 것이다.

두 번의 탈출이 있었다면, 원래 기록이 0 1 2 3 0 1 이었을 수 있고, 그 경우 2개의 기록이 조작된 것이다. 첫 번째 날과 다섯 번째 날에 탈출한 것이다.

세 번의 탈출이 있었다면, 원래 기록이 0 1 2 0 0 1 이었을 수 있고, 그 경우 1개의 기록이 조작된 것이다. 첫 번째, 네 번째, 다섯 번째 날에 탈출한 것이다.

...

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]