DMOPC '20 Contest 4 P4 - Javelin Throwing

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

Alice is training for an upcoming javelin-throwing competition! The javelin-throwing field can be modelled as a 1-D line, with Alice standing at the coordinate .

Alice throws javelins in the positive direction. When she throws a javelin, it lands at some real-valued point on the field, making a hole there. It's possible for the javelin to land exactly in a previously made hole, in which case no new hole is made. Holes are permanent, and there are initially no holes in the field.

Right after the throw, Alice counts and , the number of holes strictly behind and strictly in front of the javelin she just threw (respectively). She then tells you . You don't know anything else about her throws.

Given the information you have right after the throw, what is the minimum possible value of ?

Input Specification

The first line contains an integer , the number of throws.

The second line contains space-separated integers, .

Output Specification

Output space-separated integers. The integer should be the minimum possible value of , given that you know through .

Sample Input 1

3
0 0 2

Sample Output 1

0 0 1

Explanation for Sample 1

There are no holes in front of throw :

So the first answer is .

On throw , you know that . It's possible that both throws landed at exactly the same point, in which case there would be no holes in front of either throw:

So the second answer is .

However, you then learn that there were holes behind throw . So the second throw must have landed behind the first, and the only solution would be

Sample Input 2

6
0 1 0 3 0 2

Sample Output 2

0 0 1 2 5 6

Sample Input 3

5
0 1 2 1 2

Sample Output 3

0 0 0 1 1