Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Fun Theory

By dhruba_1603088 · Limits 3s, 512 MB

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.

Input

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.

Output

If there is no solution, print a single line “Impossible”.

Otherwise, print “Possible”.

Samples

InputOutput
3
0 0 0
Possible
InputOutput
4
0 1 2 3
Impossible


Discussion
Statistics

42% Solution Ratio

JobaidulEarliest, 1M ago

Noshin_1703086Fastest, 0.0s

iammarajulLightest, 131 kB

mahdi.hasnatShortest, 224B

Submit

Login to submit