Sticky Situation

Interview

Time limit2sMemory limit512 MB

Summary

Given N stick lengths, decide whether some three of them can form a triangle with positive area.

Level: Medium4 of 10
Topics: Sorting, Greedy
Solved: No attempts yet

Problem

You are at summer camp, playing hide-and-seek in the forest. The players need a "safe zone": if they reach it without being spotted, they beat the seeker. Picking that zone well matters.

You point at a tree, but the other players are not satisfied. Its branches stretch far in every direction, so nobody can tell when a player has reached the safe zone. They want a boundary that is exactly defined. You tell them to collect sticks, and you promise to lay three of them beside the tree as a triangle of strictly positive area, which becomes the safe zone. They come back with sticks of many different lengths, and now you do not know whether the collected sticks can form a triangle at all.

Write a program that decides whether exactly three of the collected sticks can form a triangle of strictly positive area.

Input

The first line contains the number of collected sticks $N$ ( $3 \le N \le 20000$ ).

The second line contains the $N$ stick lengths, separated by spaces. Each length is a positive integer smaller than $2^{60}$ .

Output

Print one line: possible if three of the given lengths form a triangle of strictly positive area, and impossible if they do not.

Examples2

Example 1
Input
```
3
1 1 1
```
Expected output
```
possible
```
Example 2
Input
```
5
3 1 10 5 15
```
Expected output
```
impossible
```