Problem description

Ciąg nazywamy bardzo rosnącym jeśli każdy następny jego wyraz jest co najmniej dwa razy większy od poprzedniego. Na przykład ciąg (1,3,6,20) jest bardzo rosnący, ale (1,3,5,20) nie.

Jasio zainteresował się ciągami bardzo rosnącymi, ale obawia się, że jego ulubiony ciąg taki nie jest. Ile najmniej elementów musi z niego usunąć, aby stał się bardzo rosnący? Pomóż mu!

Napisz program, który: wczyta ciąg, wyznaczy najmniejszą liczbę elementów jakie należy z niego usunąć, aby stał się bardzo rosnący i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość ciągu Jasia. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb naturalnych pooddzielanych pojedynczymi odstępami A_i – są to kolejne elementy ciągu Jasia.

Wyjście

W pierwszym (jedynym) wierszu wyjścia należy wypisać najmniejszą liczbę elementów, które należy wyrzucić z ciągu Jasia, aby stał się on bardzo rosnący.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ A_i ≤ 10¹⁸.

Przykład

8
1 3 5 6 1 4 20 8

4