409349: GYM103488 C Constructive Problem

Adam has an array $$$a$$$ consisting of $$$n$$$ integers $$$a_0, a_1, ..., a_{n-1}$$$. We call this array beautiful if the number of occurrences of $$$i$$$ is $$$a_i$$$ for $$$i\in [0,n-1]$$$.

For example:

• $$$[1,2,1,0]$$$ is beautiful. In this array, $$$0$$$ appears $$$1$$$ time, $$$1$$$ appears $$$2$$$ times, $$$2$$$ appears $$$1$$$ time, and $$$3$$$ appears $$$0$$$ times, and $$$a_0=1,a_1=2,a_2=1,a_3=0$$$.
• $$$[0,1]$$$ is not beautiful. Because $$$a_0=0$$$ but in fact $$$0$$$ appears $$$1$$$ time.

Find a beautiful array of length $$$n$$$. If there are multiple answers, output any. If there is no beautiful array of length $$$n$$$, output $$$-1$$$.

The input contains an integer $$$n$$$ $$$(1\leq n\leq 10^6)$$$ — the length of the beautiful array.

Output a beautiful array of length $$$n$$$. If there are multiple answers, output any. If there is no beautiful array of length $$$n$$$, output $$$-1$$$.

4

1 2 1 0

2

-1

In Example 1, $$$[1,2,1,0]$$$ or $$$[2,0,2,0]$$$ are both beautiful array of length $$$4$$$, and you can output any of them.