B. Double Trouble
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Ruslan recently bought a sequence of non-negative integers a1, a2, ..., an. He is a positive person, that is why he likes non-decreasing sequences. He also has an ultimate power of doubling an integer at some position by doing a single finger snap. He may perform as many finger snaps as he wants, he may also double the same integer many times.

He is curious what is the minimum number of finger snaps he has to do in order to make sequence non-decreasing. Help him find this number or tell him that it is impossible.

Input

The first line of input contains the only integer n (1 ≤ n ≤ 100 000), the length of the sequence.

The second line of input contains n integers a1, a2, ..., an (0 ≤ ai ≤ 106).

Output

If it is impossible to obtain a non-decreasing sequence of numbers by applying doubling operation, print  - 1.

Otherwise print the minimum number of finger snaps needed to obtain a non-decreasing sequence of numbers.

Examples
Input
5
3 2 1 5 4
Output
4
Input
2
1000000 0
Output
-1
Note

In the first sample test the best way to obtain a non-decreasing sequence is to double second number once, third number twice and fifth number once. At the end sequence will look like 3 4 4 5 8.