void swap(int&x,int&y)
   {
    int temp = x;
    x = y;
    y = temp;
   }

  void quicksort(int first,int last) // sorts the subarray A[first .. last]
   {
    if(first < last) // if first >= last, we are done
     {
      int mid = (first+last)/2;
      int pivot = A[mid];
      swap(A[mid],A[first]); // move pivot to first position
      int lo = first;
      int hi = last;
          // loop invariant: first+1 <= i <= lo implies A[i] <= pivot
          // and: hi < i <= last implies A[i] >= pivot
      while(lo < hi)
       {
        if(A[lo+1] > pivot and A[hi] < pivot)
         {
          swap(A[lo+1],A[hi]);
          lo++;
          hi--;
         }
        if(A[lo+1] <= pivot) lo++;
        if(A[hi] >= pivot) hi--;
       }
      //assert(lo == hi);
      swap(A[first],A[lo]); // move pivot between subarrays
      if(lo < mid) // sort the smaller subarray first
       {
        quicksort(first,lo-1);
        quicksort(lo+1,last);
       }
      else
       {
        quicksort(lo+1,last);
        quicksort(first,lo-1);
       }
     }
   }

  int main()
   {
    getA();
    cout << "Unsorted" << endl;
    printA();
    quicksort(0,n-1);
    cout << "Sorted" << endl;
    printA();
    return 1;
   }