//快排代码
    void QuickSort(vector<int> &input,int l,int r){
        if(l>=r) return;
        int M=partion(input,l,r);
        QuickSort(input,l,M-1);
        QuickSort(input,M+1,r);
    }
    int partion(vector<int> &input,int l,int r){
        int pivot=input[l];
        while(l<r){
            while(l<r&&input[r]>=pivot) r--;
                input[l]=input[r];
            while(l<r&&input[l]<=pivot) l++;
                input[r]=input[l];
        }
        input[l]=pivot;
        return l;
    }