int partition(int* a,int l,int r)
    {
    int i=l-1,j=r,v=a[r];
    while(1)
    {
    while(a[++i]<v||a[--j]>v) if(j<=i) break;
    if(i>=j)
    break;
    swap(a[i],a[j]);
    }
    swap(a[i],a[r]);
    return i;
    }
    void qsort(int* a,int l,int r)
    {
    if(l>=r) return;
    int i = partition(a,l,r);
    qsort(a,l,i-1);
    qsort(a,i+1,r);
    }