Agar.io

Interview

Time limit1.5sMemory limit1024 MB

Summary

Find the fewest absorptions for a cell starting at mass 2 to reach or match the largest opponent mass, absorbing only cells smaller than itself.

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

Problem

The game agar.io, which was fairly popular online for a while, is played in a web browser. Every player on the server controls a single cell with some mass. When a cell meets a cell with smaller mass, it absorbs it, and its mass grows by the mass of the absorbed cell. When it meets a cell with mass greater than or equal to its own, it loses immediately.

Bajtek just connected to the server, and his cell has a modest mass of 2. He would very much like to win, meaning become the largest cell on this server. Thanks to his remarkable hacking skills, he has blocked other players from moving. He can freely choose which cells to absorb, and the other players cannot avoid meeting him.

This situation will not last long. The administrators will soon lift Bajtek's block. Bajtek can absorb another cell within one second. How many seconds does he need to become the largest cell on the server? A tie with the other largest cells is acceptable to him.

Write a program that, given the masses of the cells controlled by Bajtek's opponents on the server, finds the minimum time Bajtek needs to become the largest cell in the game. Remember that Bajtek's cell starts with mass 2.

Input

The first line contains a natural number $N$ ( $1 \le N \le 200000$ ), the number of cells controlled by Bajtek's opponents. The second and last line contains $N$ natural numbers $T_i$ ( $1 \le T_i \le 10^{18}$ ), separated by single spaces. These are the masses of the opponents' cells.

Output

Print one non-negative integer, the minimum number of seconds Bajtek's cell needs to become the largest on the server, assuming the other cells do not eat each other. If this goal is impossible, print only the word NIE instead.

Examples3

Example 1
Input
```
7
1 2 2 10 5 12 1
```
Expected output
```
4
```
Example 2
Input
```
7
3 4 5 3 6 4 3
```
Expected output
```
NIE
```
Example 3
Input
```
8
1 2 4 8 16 32 64 128
```
Expected output
```
7
```