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

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 a_{i} persons wearing a mask differing from his own.

After a year, you forgot all about others’ masks, but you want to remind that. Let b_{i} be the number of mask type the i-th person was wearing, you have to find any possible b_{1},b_{2},…,b_{n} 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≤10^{5}), the number of persons in the disco.

The second line contains n integers a_{1},a_{2},…,a_{n} (0 ≤ a_{i} ≤ 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 |

42% Solution Ratio

JobaidulEarliest,

Noshin_1703086Fastest, 0.0s

iammarajulLightest, 131 kB

mahdi.hasnatShortest, 224B

Login to submit