Codeforces Round #154 (Div. 2): B - Physics Practical

// Codeforces Round #154 (Div. 2): B - Physics Practical 

import java.io.*;
import java.math.*;
import java.util.*;

//codeforces
public class Main2 {
    private static Scanner in;
    private static PrintStream out = System.out;

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        in = new Scanner(System.in);
        if (LOCAL_TEST) {
            in = new Scanner(new FileInputStream("E:\\zin2.txt"));
        }
        else {
            // using input.txt and output.txt as I/O
            in = new Scanner(new FileInputStream("input.txt"));
            out = new PrintStream("output.txt");
        }
        solve();
    }

    private static void solve()
    {
        int N = in.nextInt();
        int[] c = new int[N];
        for (int i = 0; i < N; i++) {
            c[i] = in.nextInt();
        }
        Arrays.sort(c);
        Map<Integer, Integer> cntGreaterThanX = new HashMap<Integer, Integer>();
        Map<Integer, Integer> cntLessThanX = new HashMap<Integer, Integer>();

        int lastnum = c[0];
        cntLessThanX.put(c[0], 0);
        for (int i = 1; i < N; i++) {
            if (c[i] != lastnum) {
                cntLessThanX.put(c[i], i);
                cntGreaterThanX.put(c[i - 1], N - i);
                lastnum = c[i];
            }
        }
        cntGreaterThanX.put(c[N - 1], 0);

        int minRemove = Integer.MAX_VALUE;
        for (int istart = 0; istart < N; istart++) {
            if (istart > 0 && c[istart] == c[istart - 1])
                continue;
            int remove = cntLessThanX.get(c[istart]);
            // binary search
            int L = istart;
            int R = N - 1;
            int iend = (L + R + 1) / 2;
            while (L < R) {
                iend = (L + R + 1) / 2;
                if (c[iend] == 2 * c[istart]) {
                    break;
                }
                if (c[iend] < 2 * c[istart]) {
                    L = iend + 1;
                }
                else {
                    R = iend - 1;
                }
            }
            while (c[iend] < 2 * c[istart] && iend < N - 1) {
                iend++;
            }
            while (c[iend] > 2 * c[istart]) {
                iend--;
            }
            remove += cntGreaterThanX.get(c[iend]);
            minRemove = Math.min(minRemove, remove);
        }
        out.println(minRemove);
    }
}