One day Vasya was on a physics practical, performing the task on measuring the capacitance. He followed the teacher's advice and did as much as n measurements, and recorded the results in the notebook. After that he was about to show the results to the teacher, but he remembered that at the last lesson, the teacher had made his friend Petya redo the experiment because the largest and the smallest results differed by more than two times. Vasya is lazy, and he does not want to redo the experiment. He wants to do the task and go home play computer games. So he decided to cheat: before Vasya shows the measurements to the teacher, he will erase some of them, so as to make the largest and the smallest results of the remaining measurements differ in no more than two times. In other words, if the remaining measurements have the smallest result x, and the largest result y, then the inequality y ≤ 2·x must fulfill. Of course, to avoid the teacher's suspicion, Vasya wants to remove as few measurement results as possible from his notes.

Help Vasya, find what minimum number of measurement results he will have to erase from his notes so that the largest and the smallest of the remaining results of the measurements differed in no more than two times.

Input

The first line contains integer n (2 ≤ n ≤ 105) — the number of measurements Vasya made. The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 5000) — the results of the measurements. The numbers on the second line are separated by single spaces.

Output

Print a single integer — the minimum number of results Vasya will have to remove.

Examples

Input

6
4 5 3 8 3 7


Output

2


Input

4
4 3 2 4


Output

0

Note

In the first sample you can remove the fourth and the sixth measurement results (values 8 and 7). Then the maximum of the remaining values will be 5, and the minimum one will be 3. Or else, you can remove the third and fifth results (both equal 3). After that the largest remaining result will be 8, and the smallest one will be 4.
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

public class Codeforces {

    static double Phi = (1 + Math.sqrt(5)) / 2.0;
    static int MAX = -1 >>> 1;
    static long MODL = 1_000_000_007L;
    static int MOD = 1_000_000_007;
    static void no() throws IOException {println("NO");}
    static void yes() throws IOException {println("YES");}

    static boolean testCases = false;
    static boolean DEBUG = false;

    static void main() throws Exception {
        int n = ni();
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = ni();
        }
        Arrays.sort(arr);
        debug(Arrays.toString(arr));
        int best = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            debug("hocc for " + arr[i] + " is index " + hocc(arr, i));
            best = Math.min(best, i + (n - 1 - hocc(arr, i) + 1));
        }
        println(best);
    }
    static int hocc(Integer[] arr, int index) {
        int lo = Math.min(index + 1, arr.length);
        int hi = arr.length - 1;
        int mid;
        int ans = arr.length;
        while(lo <= hi) {
            mid = lo + (hi - lo >> 1);
            if(arr[mid] > arr[index] << 1) {
                //nice ans .. go lower
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return Math.min(arr.length, ans);
    }

    public static void main(String[] args) throws Exception {
        long startPointTime = System.currentTimeMillis();
        scannerIn = new FileInputStream("input.txt");
        printerBW = new BufferedWriter(new OutputStreamWriter(new FileOutputStream("output.txt")));
        if (DEBUG && System.getProperty("ONLINE_JUDGE") == null) {
            HABLA = true;
            debug("Debugging enabled");
        }

        int t = testCases ? ni() : 1;
        int to = t;
        while (t-- > 0) {
            debug("Case #" + (to - t) + " ---------------- ");
            main();
        }
        long endTime = System.currentTimeMillis();
        float totalProgramTime = endTime - startPointTime;
        if (HABLA)
            debug("Execution time is " + totalProgramTime + " (" + (totalProgramTime / 1000) + "s)");
        close();
    }

    //IO Stuff
    private static boolean HABLA = false;
    private static byte[] scannerByteBuffer = new byte[1024]; // Buffer of Bytes
    private static int scannerIndex;
    private static InputStream scannerIn;
    private static int scannerTotal;
    private static BufferedWriter printerBW;

    private static int next() throws IOException { // Scan method used to scan buf
        if (scannerTotal < 0)
            throw new InputMismatchException();
        if (scannerIndex >= scannerTotal) {
            scannerIndex = 0;
            scannerTotal = scannerIn.read(scannerByteBuffer);
            if (scannerTotal <= 0)
                return -1;
        }
        return scannerByteBuffer[scannerIndex++];
    }

    static int ni() throws IOException {
        int integer = 0;
        int n = next();
        while (isWhiteSpace(n)) // Removing startPointing whitespaces
            n = next();
        int neg = 1;
        if (n == '-') { // If Negative Sign encounters
            neg = -1;
            n = next();
        }
        while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
                integer *= 10;
                integer += n - '0';
                n = next();
            } else
                throw new InputMismatchException();
        }
        return neg * integer;
    }

    static long nl() throws IOException {
        long integer = 0;
        int n = next();
        while (isWhiteSpace(n)) // Removing startPointing whitespaces
            n = next();
        int neg = 1;
        if (n == '-') { // If Negative Sign encounters
            neg = -1;
            n = next();
        }
        while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
                integer *= 10;
                integer += n - '0';
                n = next();
            } else
                throw new InputMismatchException();
        }
        return neg * integer;
    }

    static String line() throws IOException {
        StringBuilder sb = new StringBuilder();
        int n = next();
        while (isWhiteSpace(n))
            n = next();
        while (!isNewLine(n)) {
            sb.append((char) n);
            n = next();
        }
        return sb.toString();
    }

    private static boolean isNewLine(int n) {
        return n == '\n' || n == '\r' || n == -1;
    }

    private static boolean isWhiteSpace(int n) {
        return n == ' ' || isNewLine(n) || n == '\t';
    }

    static int[] nia(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        final int[] array = new int[n];
        for (int i = 0; i < n; ++i)
            array[i] = ni();
        return array;
    }

    static Integer[] __nia__(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        final Integer[] array = new Integer[n];
        for (int i = 0; i < n; ++i)
            array[i] = ni();
        return array;
    }

    static Long[] __nla__(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        final Long[] array = new Long[n];
        for (int i = 0; i < n; ++i)
            array[i] = nl();
        return array;
    }

    static int[][] n2dia(int r, int c) throws Exception {
        if (r < 0 || c < 0)
            throw new Exception("Array size should be non negative");
        int[][] array = new int[r][c];
        for (int i = 0; i < r; i++)
            array[i] = nia(c);
        return array;
    }

    static long[] nla(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        long[] array = new long[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static float[] nfa(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        float[] array = new float[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static double[] nda(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        double[] array = new double[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static <T> void print(T str) {
        try {
            printerBW.append(str.toString());
        } catch (IOException e) {
            System.out.println(e);
        }
        if (HABLA) flush();
    }

    static <T> void println() {
        try {
            printerBW.append('\n');
        } catch (IOException e) {
            System.out.println(e);
        }
        if (HABLA) flush();
    }

    static <T> void println(T str) {
        try {
            if (str == null) {
                printerBW.append("null\n");
            } else {
                printerBW.append(str.toString());
                printerBW.append('\n');
                if (HABLA) flush();
            }
        } catch (IOException e) {
            System.out.println(e);
        }
    }

    public static final String ANSI_RESET = "\u001B[0m";
    public static final String ANSI_DEBUG = "\u001B[33m";
    static <T> void debugl(T str) {
        if (!HABLA) return;
        try {
            if (str == null) {
                printerBW.append(ANSI_DEBUG);
                printerBW.append("null");
                printerBW.append(ANSI_RESET);
            } else {
                printerBW.append(ANSI_DEBUG);
                printerBW.append(str.toString());
                printerBW.append(ANSI_RESET);
            }
        } catch (IOException e) {
            System.out.println(e);
        }
        flush();
    }

    static void debug() {
        if (!HABLA) return;
        try {
            printerBW.append('\n');
        } catch (IOException e) {
            System.out.println(e);
        }
        flush();
    }
    static <T> void debug(T str) {
        if (!HABLA) return;
        try {
            if (str == null) {
                printerBW.append(ANSI_DEBUG);
                printerBW.append("null\n");
                printerBW.append(ANSI_RESET);
            } else {
                printerBW.append(ANSI_DEBUG);
                printerBW.append(str.toString());
                printerBW.append(ANSI_RESET);
                printerBW.append('\n');
            }
        } catch (IOException e) {
            System.out.println(e);
        }
        flush();
    }

    static void flush() {
        try {
            printerBW.flush();
        } catch (IOException e) {
            System.out.println(e);
        }
    }

    static void close() {
        try {
            printerBW.close();
        } catch (IOException e) {
            System.out.println(e.toString());
        }
    }
}