D. Discception
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Christoph Clavius, Astrolabium (1593), Book II, Proposition VI, p. 419. Public domain, via Archive.org, scan by University of Michigan

After Ferdinand Magellan's expedition, it became clear to everyone in Europe what scholars and the ancient Greeks had known for a long time: the Earth was, indeed, not a disc.

Less well known is that, around the same time, European scholars were working on a much more ambitious theory of the motion of the celestial bodies. Astronomers often described planetary motion using deferents and epicycles, circles whose centres themselves moved along other circles. Some scholars took this idea further and hypothesized that a system of circular orbits was stable precisely when the centre of every orbit lay on another orbit in the same system.

Today we know that celestial mechanics are somewhat more complicated than that.

From their observations, the scholars calculated the radii of the circles needed for their model, but not their positions. Therefore, they wanted to know whether these circles could be arranged in a stable manner, that is, so that the centre of every circle lies on the circumference of another circle.

Checking all possible arrangements by hand was rather inconvenient, but fortunately, we now have computers to determine whether such an arrangement is possible.

A stable arrangement for the third sample. Each dot marks the centre of the circle with the corresponding colour.
Input

The input consists of:

  • One line with an integer $$$n$$$ ($$$2\leq n\leq {2 \cdot 10^5}$$$), the number of radii.
  • One line with $$$n$$$ integers $$$r$$$ ($$$1\le r\le {10^9}$$$), the radius of each circle.
Output

If it is possible to arrange the circles in a stable manner, output "possible". Otherwise, output "impossible".

Examples
Input
3
1 1 1
Output
possible
Input
2
1 2
Output
impossible
Input
6
7 2 1 4 3 5
Output
possible