For a chat application, a team of developers needs to study the different message writing patterns of the users. Some users write long messages and some users write short messages. As a part of the study the developers have a sequence of lengths of N messages in their system in the order in which these were sent in a chat by the users. The developer must select a homogenous sequence such that the maximum length of a message is less than double the minimum length of a message in the selected sequence. For selection, only the messages from one of the ends of the sequence can be removed. The system must remove the minimum number of messages while fulfilling the developer's requirement.

Write an algorithm to find the minimum number of messages that must be removed so that the maximum length of a message is less than double the minimum length of a message in the final selected sequence.

Input

The first line of the input consists of an integer-msglist size representing the number of selected messages from a chat (N)

The next line consists of N space-separated integers — msgList[0], msgList[1] .....msgList[N-1], representing the length of messages,

Output

Print an integer representing the minimum number of messages that must be removed after selecting a sequence such that the maximum length of a message is less than double the minimum length of a message in the selected sequence.

Constraints

0<=msglist_size<=10^4

0<msgList[0], msgList[1] ,......msgList[N-1)<1000

Example

Input:

5

22 5 4 7 15

Output

2