JMU F18 Week 10

Start

2018-11-02 18:30 UTC

JMU F18 Week 10

End

2018-11-08 21:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -11 days 2:14:46

Time elapsed

146:30:00

Time remaining

0:00:00

Problem D
Sticky Situation

While on summer camp, you are playing a game of hide-and-seek in the forest. You need to designate a “safe zone”, where, if the players manage to sneak there without being detected, they beat the seeker. It is therefore of utmost importance that this zone is well-chosen.

You point towards a tree as a suggestion, but your fellow hide-and-seekers are not satisfied. After all, the tree has branches stretching far and wide, and it will be difficult to determine whether a player has reached the safe zone. They want a very specific demarcation for the safe zone. So, you tell them to go and find some sticks, of which you will use three to mark a non-degenerate triangle (i.e. with strictly positive area) next to the tree which will count as the safe zone. After a while they return with a variety of sticks, but you are unsure whether you can actually form a triangle with the available sticks.

Can you write a program that determines whether you can make a triangle with exactly three of the collected sticks?

Input

The first line contains a single integer $N$, with $3 \leq N \leq 20\, 000$, the number of sticks collected. Then follows one line with $N$ positive integers, each less than $2^{60}$, the lengths of the sticks which your fellow campers have collected.

Output

Output a single line containing a single word: possible if you can make a non-degenerate triangle with three sticks of the provided lengths, and impossible if you can not.

Sample Input 1 Sample Output 1
3
1 1 1
possible
Sample Input 2 Sample Output 2
5
3 1 10 5 15
impossible