Time limit: 5000ms
Memory limit: 256mb

Description:
In this exercise, you are required to complete the function QuickSort which sorts some integers in descending order. You can find the pseudocode in lecture notes. (ch6.pptx)

1. Sort the array in descending order.

You can assume that all the integers of A[] after sorting may not distinct, which means that A[0] >= A[1] >= … >= A[n-1].

The code template has been provided. Your task is to complete the following functions.

void QuickSort(int A[], int left, int right)
Example:
You have an array A before sorting: [1,2,6,5,1,7], then this function is called to sort A[left]...A[right] in descending order. 
The result array should be [7,6,5,2,1,1]

You could declare some variables yourself in the functions. However, you are not allowed to use any addtional array to do the partition.

Sample Input 1:
10
2 1 4 10 3 5 7 8 9 6

Sample Output 1:
10 9 8 7 6 5 4 3 2 1

Sample Input 2:
5
1 2 1 2 1

Sample Output 2:
2 2 1 1 1

Code Template:

#include <stdio.h>
#include <stdlib.h>

void PrintArray(int A[], int n)
{
    for(int i=0; i<n; i++)
        printf("%d ", A[i]);
    printf("\n");
}

void QuickSort(int A[], int left, int right)
{
    if(left<right)
    {
        int PivotValue = A[left];
        /*
            Fill in your code here.
            You can add some variables but no additional array.
        */
    }
}

int main()
{
    int n, *a;
    scanf("%d",&n);
    a = (int*)malloc(sizeof(int)*n);
    for(int i=0; i < n; i++)
        scanf("%d", &a[i]);
        
    QuickSort(a, 0, n-1);
    PrintArray(a, n);
    return 0;
}