from US Navy, public domain
Linda is giving an exam. When the exam is over, Linda will
redistribute the exams among the students for a peer review, so
they may grade each other’s answers and assign preliminary
The students are split up in several rooms of varying sizes.
Linda has devised the following scheme for redistributing the
Linda visits the first room, picks up all exams written
there, and places them in a pile.
In each subsequent room Linda takes exams from the top
of her pile and randomly distributes them to the students
in the room. She then picks up all exams written in that
room and adds them to the bottom of her pile.
After having visited each room exactly once, Linda
returns to the first room, and distributes the remaining
exams from her pile there.
Naturally, it is imperative that no student receives their
own exam to review, and that Linda does not run out of exams in
her pile while doing the redistribution (i.e., that when
entering a room after the first one, Linda’s pile contains at
least as many exams as there are students in the room). Whether
or not this is the case depends on the order in which the rooms
are visited. We say that an ordering of the rooms is
safe if Linda will not run out of exams in her pile
when visiting rooms in that order, and that there is no chance
that any student receives their own exam to review.
Can you find a safe order in which to visit the rooms (or
determine that no safe order exists)?
The input consists of:
one line containing an integer $n$ ($2 \le n \le 30$), the number of
one line containing $n$ integers $s_1, \ldots , s_ n$ ($1 \le s_ i \le 100$ for each
$s_ i$ is the number
of students in room $i$.
If it is impossible to redistribute the exams safely, output
“impossible”. Otherwise, output a
safe order in which to visit the rooms. If there are multiple
safe orders, you may give any of them.
|Sample Input 1
||Sample Output 1
2 3 3 1
2 3 4 1
|Sample Input 2
||Sample Output 2