Mảng dày (Dense Array)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một dãy số nguyên dương được gọi là dày nếu với mọi cặp kề nhau, số lớn hơn không vượt quá hai lần số nhỏ hơn. Bạn được chèn các số nguyên dương vào bất kỳ vị trí nào nhưng không được đổi thứ tự các phần tử ban đầu. Hãy tìm số phần tử ít nhất cần chèn để dãy trở thành dày.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số $a_1,\ldots,a_n$.

Output

In số phần tử ít nhất cần chèn.

Subtask

Các giới hạn chung:

• $2 \le n \le 50$.

• $1 \le a_i \le 50$.

• Subtask 1 (20 điểm): $n \le 10$, $a_i \le 10$

• Subtask 2 (30 điểm): $n \le 30$, $a_i \le 30$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

4
4 2 10 1

Output

5

Giải thích

Cặp $(4,2)$ đã hợp lệ. Giữa $2$ và $10$ cần hai mắt xích; giữa $10$ và $1$ cần ba mắt xích. Tổng cần chèn $5$.