Comso Christmas

Interview

Time limit2sMemory limit1024 MB

Summary

Decide if N problems, each needing s_i wrong answers before its accepted verdict, can be submitted so that verdicts alternate, starting with Accepted.

Level: Medium5 of 10
Topics: Greedy, Sorting, Prefix sum
Solved: No attempts yet

Problem

The Department of Computer Science and Software has a tradition of decorating each Christmas's submission status like a Christmas tree. Specifically, when all submissions from a given day are collected, that day's submissions are said to be decorated like a Christmas tree if all of the following conditions hold.

Every submission's verdict is either "Accepted!!" or "Wrong Answer".
When the submissions are listed in time order, the first submission's verdict is "Accepted!!".
Every submission other than the first has a verdict different from the one right before it. For example, the second submission is "Wrong Answer", the third is "Accepted!!", and so on, $\cdots$

Input

On Christmas, Arami will solve all $N$ problems. The problems are numbered from 1 to $N$ . Arami always follows these rules while solving.

Arami submits only code whose verdict is "Accepted!!" or "Wrong Answer".
Arami does not resubmit a problem that has already been solved.

To keep the Comso tradition, Arami wants to decorate the day's submission status like a Christmas tree. All-knowing participants can tell exactly how many times Arami got "Wrong Answer" on each problem before solving it. Write a program that determines whether Arami can receive "Accepted!!" on all $N$ problems while the submissions are decorated like a Christmas tree. If it can, print the order in which the submissions should be made.

Output

The first line contains the number of problems $N$ that Arami will solve. $(1\leq N\leq 200\,000)$

From the second line on, $N$ integers $s_1, s_2, \cdots, s_N$ are given, one per line. $s_i$ means that Arami solves problem $i$ after getting "Wrong Answer" $s_i$ times. In other words, Arami can submit problem $i$ at most $s_i+1$ times, gets "Accepted!!" on the $(s_i+1)$ -th submission, and gets "Wrong Answer" on the rest. $(0\le s_i\le 10^9)$

Examples3

Example 1
Input
```
2
1
0
```
Expected output
```
2
1
1
```
Example 2
Input
```
2
2
0
```
Expected output
```
-1
```
Example 3
Input
```
5
0
0
1
2
1
```
Expected output
```
2
4
1
5
5
3
3
4
4
```