Double

Interview

Time limit1sMemory limit1024 MB

Summary

Given a sequence of positive integers, find the fewest doublings of single elements needed to make the sequence non-decreasing.

Level: Easy3 of 10
Topics: Greedy, Math
Solved: No attempts yet

Problem

A sequence of positive integers $A_1, \dots, A_N$ of length $N$ is given. You want to make this sequence ascending. The sequence $A_1, \dots, A_N$ is ascending if $A_i \le A_{i+1}$ holds for each $i$ ( $1 \le i \le N-1$ ).

To make $A$ ascending, you can apply the following operation any number of times.

Multiply $A_i$ by $2$ for some $i$ ( $1 \le i \le N$ ).

You want to make $A$ ascending with the fewest operations. Find that minimum number of operations.

Input

The first line contains $N$ .

The second line contains $A_1, \dots, A_N$ .

Output

Print the answer on the first line.

Constraints

All given numbers are integers.
$1 \le N \le 250\,000$
$1 \le A_i \le 1\,000\,000$ ( $1 \le i \le N$ )

Examples3

Example 1
Input
```
5
3 1 4 1 5
```
Expected output
```
4
```
Example 2
Input
```
5
3 1 5 1 5
```
Expected output
```
6
```
Example 3
Input
```
5
1 2 3 4 5
```
Expected output
```
0
```