409812: GYM103785 G Dualites in Pain - The Conclusion

This is the same problem as the previous version (problem C). The only difference is in the output - now you have to output the sequence of lectures to be watched, too.

My dualite fiends, and Mithil, have been crying all semester long about their tiresome courses and no time to study. So I now help them draft a schedule that they will never follow :)

There are $$$N$$$ courses that they have this semester, and for each course, they require $$$a_i$$$ lectures to binge.

Each of my fiends has a compulsive need to watch the lectures of that course first which has the most unwatched lectures. Also, the dumdums that they are, they cannot watch two consecutive lectures of the same course!

Given the array containing the lectures of each course - your task is to find out whether my fiends would be able to watch all those lectures or not - and if they indeed can, print a suitable order of lectures that they can watch.

Note : In case there are multiple possible solutions, print the lexicographically least one. That is, if two lectures can be chosen at the same time, choose the lecture with the lower index first.

The first line of input consists of a single number $$$N$$$ $$$(2 \leq N \leq 100)$$$ - the number of courses. I know right! 100 courses!! They do make it sound like a 100 though ;)

The second line contains $$$N$$$ space separated integers $$$a_i$$$ $$$(1 \leq a_i \leq 1000)$$$ - the elements of array $$$a$$$ - representing the lectures of the $$$i$$$th course. Again, 1000 lectures! RR hai ye bas.

Print $$$-1$$$ if it is not possible for them to watch all lectures.

Otherwise print $$$(\sum_{i=1}^{N}a_i$$$) numbers. This array of numbers represents the order in which the lectures should be binged. The $$$i$$$th number is the index $$$(1 \leq index \leq N)$$$ of the course whose lecture should be watched next.

If there are multiple courses with the same number of lectures to be watched - the lecture of the course with the lower index should be watched first.

5
1 2 3 4 5

5 4 5 3 4 5 2 3 4 5 1 2 3 4 5 

5
1 2 3 4 12

-1