Let's go for a short statement.
n people took part in a disco. To make the disco scarier, each person wore one mask among n kinds of scary masks numbered 1,2,…,n. It is possible that several persons wore masks of the same kind. Some kinds of masks can remain unclaimed by anyone.
After the disco ended, the i-th person said that there were ai persons wearing a mask differing from his own.
After a year, you forgot all about others' masks, but you want to remind that. Let bi be the number of mask type the i-th person was wearing, you have to find any possible b1,b2,…,bn that doesn't contradict with any person's statement. Some persons might have lied. In that case there could be no solution at all.
The first line contains a single integer n (1≤n≤105), the number of persons in the disco.
The second line contains n integers a1,a2,…,an (0 ≤ ai ≤ n−1), the statements of people.
If there is no solution, print a single line "Impossible".
Otherwise, print "Possible".
| Input | Output |
|---|---|
3 0 0 0 | Possible |
| Input | Output |
|---|---|
4 0 1 2 3 | Impossible |