static Random rand = new Random();
    static void qsort(int[] a, int l, int r){
        int k = rand.nextInt(r - l) + l;
        int key = a[k];
        int i = l;
        int j = r;
        while(i <= j){
            while(a[i] < key)
                i++;
            while(key < a[j])
                j--;

            if(i <= j){
                swap(a, i, j);
                i++;
                j--;
            }
        }

        if(l < j)
            qsort(a, l, j);
        if(i < r)
            qsort(a, i, r);
    }

    static void swap(int[] a, int i, int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }