Problem H

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.


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 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
1 2 3
Sample Input 2 Sample Output 2
1 2 3 4 5
Sample Input 3 Sample Output 3
1 2 3 4 5 6

Please log in to submit a solution to this problem

Log in