All submissions for this problem are available.
Suppose students are standing in a queue for the Sunday ice-cream in IISc Mess. They all like ice-cream and each one has some amount of rupees with them. A student gets really upset when there is someone with strictly less money standing in the queue in front of them.The students follow a protocol that anyone can pay 1 rupee (if he/she has it) to the person standing just in front of them and exchange places. The goal is to make every student happy by making these 1 rupee swaps. A student is happy when he/she is the first in the queue, or if the person in front of them in the queue have greater or equal amount of rupee than them. Note that you are only allowed to change places by making these 1 rupee swaps, where a student pays 1 rupee to the person just in front of him/her to change places. Input: The first line contains integer N (1≤N≤2000) — the number of students in the queue. The second line contains N space-separated integers a_i (0≤a_i≤10^9), where a_i is the number of rupees of a student standing on the i-th position in the line. The positions are numbered starting from the end of the line.(Ice cream counter on right end and numbering starts from left end) Output: If it is impossible to make all the students happy, print ":(" without the quotes. Otherwise, print in the single line N space-separated integers, the i-th integer must be equal to the amount of money the student has, standing at position 'i' in the new line. If there are multiple answers, print any of them. Sample test(s) input 2 11 8 output 9 10 input 5 10 9 7 10 6 output :( input 3 12 3 3 output 4 4 10 Note In the first sample two students should swap places, after that the first student has 10 rupees and he is at the head of the line and the second student will have 9 rupees and he will be at the end of the line. In the second sample it is impossible to achieve the desired result. In the third sample the first student can swap with the second one, then they will have the following numbers of dollars: 4 11 3, then the second student (in the new line) swaps with the third one, and the resulting numbers of rupees will equal to: 4 4 10. In this line everybody will be happy.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.