Dense Array

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

A positive integer array is dense if, for every adjacent pair, the larger value is at most twice the smaller one. You may insert positive integers anywhere without changing the order of the original elements. Find the minimum number of inserted elements needed to make the array dense.

Input

The first line contains $n$. The second line contains $a_1,\ldots,a_n$.

Output

Print the minimum number of inserted elements.

Subtasks

General constraints:

• $2 \le n \le 50$.

• $1 \le a_i \le 50$.

• Subtask 1 (20 points): $n \le 10$, $a_i \le 10$

• Subtask 2 (30 points): $n \le 30$, $a_i \le 30$

• Subtask 3 (50 points): No additional constraints.

Examples

Input

4
4 2 10 1

Output

5

Explanation

The pair $(4,2)$ is already dense. Two values are needed between $2$ and $10$, and three between $10$ and $1$, for a total of $5$.