OpenKattis
CS3233 Midterm Team Contest

Start

2019-04-01 09:00 UTC

CS3233 Midterm Team Contest

End

2019-04-01 13:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -226 days 2:58:04

Time elapsed

4:30:00

Time remaining

0:00:00

Problem H
Hearthbreakers

Pinkie Pie and Applejack are celebrating Hearth’s Warming Eve together, and as per tradition, they will be serving rock soup—delicious, nutritious and scrumdiddlyumptious!

To prepare the rock soup, they first need to prepare $N$ rocks of the appropriate sizes, catering to the appetites of each pony. The rocks should have integer sizes $S_1, S_2, S_3, \dots , S_ N$.

According to Hearth’s Warming tradition, they must obtain these rocks by starting with a single, giant rock of some integer size $m$.

Denote by $\lfloor x\rfloor $ the largest integer not greater than $x$, and $\lceil x \rceil $ the smallest integer not less than $x$.

When a rock of size $s > 1$ is struck with a pickaxe, it breaks and two rocks, with sizes $\lfloor \frac{s}{2}\rfloor $ and $\lceil \frac{s}{2}\rceil $, are produced. Note that rocks of size $1$ cannot be broken further.

\includegraphics[width=0.5\textwidth ]{hearthbreakers.png}
Figure 1: Illustration of Sample Input 1.

Is it possible to produce all the desired rocks? If so, what is the smallest size $m$ they should use? Note that not all of the rocks produced have to be used for the rock soup; there can be some leftover rocks.

Input

The first line of input contains a single integer $N$ ($2 \leq N \leq 200\, 000$), the number of rocks they need.

The second line of input contains $N$ integers, $S_1, S_2, \dots , S_ N$ ($1 \leq S_ i \leq 10^9$), the sizes of the rocks they need.

Output

Output on a line by itself:

  • the smallest positive integer $m$ that can produce all the desired rocks, if such $m$ exists, or

  • IMPOSSIBLE, otherwise.

The input will be such that if $m$ exists, then $m \leq 10^{18}$.

Sample Input 1 Sample Output 1
3
1 2 3
6
Sample Input 2 Sample Output 2
5
1 2 3 4 5
18
Sample Input 3 Sample Output 3
6
1 2 3 4 5 6
IMPOSSIBLE