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

John has invested in this great app designed by Big Head that can help scale big restaurants: The restaurants have N customers which are represented by an array A of size N*3 where arrival time, departure timer, and the number of dishes X ordered by the customer are denoted by the row of array A

The app calculates the minimum number of chefs the restaurant needs to hire to make dishes to fulfill the orders of all N customers. One chef can only make one dish in one unit of time and each dish takes a unit of time to be prepared.

Help John to determine the minimum number of chefs required

to fulfill the orders of all the N customers.

Parameters description

N. Represents the number of customers

A Represents the array that denotes the details of the N customers

Constraints: 1<=N <=2*10^5 1<=l<=r<=10^9 1<=X<=10^9

Given a string consisting of lowercase English alphabets of length N

Consider each proper prefix of length from 1 to N-1 and compare that prefix with each of the other same-length substrings lexicographically except the prefix itself.

For each prefix of length from 1 to N-1 ,compare that prefix with each of the same length substrings, and determine how many substrings are greater, equal, and smaller than that prefix respectively.

Notes A substring is a contiguous sequence of characters within a string .For example the list of all non-empty substrings of the string "apple" would be "apple", "appl" ,"pple" ,"app", "ppl" ,"ple","ap" ,"pp" ,"pl", "le" ,"a","p" ,"l","e". A prefix of a string S is a substring that occurs at the beginning of S.

Input format:

The fist line consists of an integer N The second fine consists of a string S of length N

Output format Print N-1 lines. The ith line denotes the answers for the prefix length i. Each line will have 3 integers denoting the count of lexicographically greater substrings, equal substrings, and smaller substrings, respectively.

Constraints 2≤ N ≤ 1e5 String S consists of lowercase English letters.

Sample Input: 5 abcba

Sample Output:

3 1 0

3 0 0

2 0 0

1 0 0

I know that the equal strings can be found by using KMP algorithm, but how to solve for lexographically smaller/larger?