405062: GYM101773 B Double Trouble

Ruslan recently bought a sequence of non-negative integers a₁, a₂, ..., a_n. 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.

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 a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁶).

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.

5
3 2 1 5 4

4

2
1000000 0

-1

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.