Migrated from Lutece 1298 Cell

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

People discovered a new type of cell.

In every second, it may grow up $1$ unit, or randomly split into two cells.

Some times ago, one person cultivate a cell in $1$ unit, and now he find that it splited into $n$ cells.

He want to know the elapsed time.

Input

The first line contains a number $n (1 \le n \le 10^5)$, indicating the number of cells.

The second line contains $n$ numbers $size_i (1 \le size_i \le 10^9)$, indicating the size of each cells.

Output

In the first line output the number of time intervals $k$.

Then $k$ lines, each line output two numbers, indicating the starting and ending time of each time intervals. Every second in the time intervals are all possible time for cells to grow into that state.

If the cells can not grow into that state, just output -1.

Samples

2
2 5

1
6 7

4
4 5 3 4

1
8 17

Resources

The 14th UESTC Programming Contest Preliminary