static int PartSort(int[] arr, int left, int right)
{
    int pivot = arr[left];
    int i = left + 1;
    int j = right;
    
    while (true)
    {
        while (i <= j && arr[i] <= pivot)
            i++;
        while (i <= j && arr[j] >= pivot)
            j--;
        if (i < j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        else
        {
            break;
        }
    }
    int pos = j;
    arr[left] = arr[pos];
    arr[pos] = pivot;

    return pos;
}

 static int PartSort(int[] array, int left, int right) {
    int target = array[left];
    int length = right - left + 1;
    int index = left;
    for (int i = 1; i < length; i++) {
        for (int j = length - 1; j >= i; j--) {
            if (array[left + j] > array[left + j - 1]) continue;
            if (left + j == index) {
                index--;
            } else if (left + j - 1 == index) {
                index++;
            }
            int temp = array[left + j - 1];
            array[left + j - 1] = array[left + j];
            array[left + j] = temp;
        }
    }
    return index;
}

 static int PartSort(int[] arr, int stP, int endP) {
    var el = arr[stP];

    Array.Sort(arr, stP, endP - stP);
    return Array.IndexOf(arr, el);
}

 static int PartSort(int[] arr, int start, int fin){
    int place = start;
    fin--;
    while(true){
        while (arr[start]<=arr[place]) start++;
        while (arr[fin]>arr[place]) fin--;
        if (start < fin) Change(start, fin);
        else break;
    }
    Change(fin, place);
    return fin;
    
    void Change(int s, int f){
        int temp=arr[s];
        arr[s]=arr[f];
        arr[f]=temp;
    }
}

 static int PartSort(int[] arr, int a, int b)
        {
            static void Change(int i,int j, int[] arr)
            {
                int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
            }
            // позиція опорного елемента
            int p = a;
            b--;
            while (true)
            {
                while (arr[a] <= arr[p]) a++;
                while (arr[b] > arr[p]) b--;
                if (a < b)
                    Change(a,b,arr);
                else
                    break;
            }
            Change(b,p,arr);
            return b;
        }

 static int PartSort(int[] arr, int left, int rigth)
{
    static void change(int a, int b, int[] arr)
    {
        int y = arr[a];
       arr[a] = arr[b];
        arr[b] = y;
    }
    int p = left;
    rigth--;
    while(true)
    {
        while(arr[left]<=arr[p]) left++;
        while(arr[rigth]> arr[p]) rigth--;
        if(left< rigth)
        {
            change(left,rigth,arr);
        }
        else
        {
            break;
        }
    }
    change(rigth, p,arr);
    return rigth;
}

 static int PartSort(int[] arr, int b1, int b2) 
{
    int tmp;
    for (int i = b1; i < b2; i++)
    {
        for (int j = i + 1; j < b2; j++)
        {
            if (arr[i] > arr[j]) 
            {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    tmp = arr[b1];
    return tmp;
}

 static int PartSort(int[] arr, int start, int end)
{
    int a = start;
    int temp;
    end--;
    while (true)
    {
        while (arr[start] <= arr[a]) start++;
        while (arr[end] >= arr[a]) end--;
        if (start < end)
        {
            temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        else 
            break;
        
    }
    temp = arr[end];
    arr[end] = arr[a];
    arr[a] = temp;
    return a;
}

 static int PartSort( int[] arr, int r, int l)
        {
            for(int i=l+1; i<=r; i++)
            {
                int elm = arr[i];
                while(arr[i]< arr[i - 1])
                {
                    int p = arr[i];
                    arr[i] = arr[i - 1];
                    arr[i - 1] = p;

                }
            }
            return arr[l];
        }

 static int PartSort(int[] arr, int a,int b){
    Array.Sort(arr,a,b);
    return arr[a];
}

 static int PartSort(int[] arr, int low, int high)
    {
        int pivot = arr[low];
        int i = low;
        int j = high;

        while (i < j)
        {
            while (i <= high && arr[i] <= pivot)
                i++;

            while (arr[j] > pivot)
                j--;

            if (i < j)
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        arr[low] = arr[j];
        arr[j] = pivot;

        return j;
    }

 static int PartSort(int[] arr, int left, int right)
{
    int pivot = arr[left]; 
    int i = left + 1;
    int j = right;

    while (i <= j)
    {
        while (i <= j && arr[i] <= pivot) i++; 
        while (i <= j && arr[j] > pivot) j--; 

        if (i < j) 
        {
            int temp = arr[i]; 
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int pivotIndex = left;
    if (arr[left] > arr[j]) 
    {
        arr[left] = arr[j]; 
        arr[j] = pivot;
        pivotIndex = j;
    }

    return pivotIndex;
}

static int PartSort(int[] arr, int s, int e) {
    int p = s;
    int tmp;
    while(true) {
        while(arr[s] <= arr[p]) s++;
        while(arr[e] > arr[p]) e--;
        if(s < e) {
            tmp = arr[s];
            arr[s] = arr[e];
            arr[e] = tmp;
        } else {
            break;
        }
    }
    return e;
}

 static int PartSort(int[] array, int a1, int a2){
    return 0;
}

 public static int PartSort(int[] arr, int left, int right)
{
    int pivotIndex = left;
    int pivotValue = arr[left];

    for (int i = left + 1; i <= right; i++)
    {
        if (arr[i] < pivotValue)
        {
            pivotIndex++;
            Swap(arr, i, pivotIndex);
        }
    }

    Swap(arr, left, pivotIndex);

    return pivotIndex;
}

private static void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 static int PartSort(int[] arr, int a, int b) {
    Array.Sort(arr, a, b);
    return arr[a];
}

 static int PartSort(int[] arr, int left, int right)
{
    int pivot = arr[left];
    int i = left + 1;
    for (int j = left + 1; j <= right; j++)
    {
        if (arr[j] < pivot)
        {
            Swap(ref arr[i], ref arr[j]);
            i++;
        }
    }
    Swap(ref arr[left], ref arr[i - 1]);
    return i - 1;
}

static void Swap(ref int a, ref int b)
{
    int temp = a;
    a = b;
    b = temp;
}

 static int PartSort(int[] arr, int left, int right){
    int[] new_arr = new int[right-left+1];
    int elem = arr[left];
    int counter = 0;
    
    for(int i = left; i < right; i++){
        new_arr[counter] = arr[i];
        counter++;
    }
    
    Array.Sort(new_arr, (x, y) => x.CompareTo(y));
    return Array.IndexOf(new_arr, elem);
}

 static int PartSort(int[] arr, int lcr, int rcr){
    int val = arr[lcr];
    int[] arr2 = new int[rcr-lcr+1];
    for(int  i = 0; i<= rcr-lcr; i++){
        arr2[i] = arr[lcr+i];
    }
    Array.Sort(arr2);
    for(int i = 0; i< arr2.Length; i++){
        if(arr2[i] == val) return i;
    }
    return 0;
}

 static int PartSort(int[] arr, int left, int right)
{
    int pos = left;
    right--;
    while (left < right)
    {
        while (arr[left] <= arr[pos]) {left++;}
        while (arr[right] > arr[pos]) {right--;}
        int temp = arr[right];
        arr[right] = arr[left];
        arr[left] = temp;
    }
    int t = arr[right];
    arr[right] = arr[pos];
    arr[pos] = t;
    return right;
}

 static void swap(ref int a, ref int b)
        {
            var temp = a;
            a = b;
            b = temp;
        }
        static int PartSort(int []arr, int l, int r)
        {
            for (int i = l; i <= r; i++)
            {
                for(int j = r; j >i; j--)
                {
                    if (arr[j] < arr[j-1]) swap(ref arr[j],ref arr[j-1]);
                }
            }

            return arr[l];
        }

 static int PartSort(int[] arr, int left, int right) {
    int res = 0;
    for (int i = left; i <= right; i++)
        if (arr[i] < arr[left]) res++;
    return res;
}

 static int PartSort(int[] structures, int firstIndex, int lastIndex){
    for (int i = firstIndex; i < lastIndex-1; i++)
    {
        if (structures[i] < structures[i+1])
        {
            int tmp= structures[i];
            structures[i]= structures[i+1];
            structures[i+1]= tmp;
        }
    }
    return structures[firstIndex];
}

 static int PartSort(int[] arr,int a,int b){
    int res=0;
    for(int i=a;i<=b;i++){
        if(arr[i]< arr[a]){
            res++;
        }
    }
    return res;
}

 static int PartSort(int[] arr, int a,int b){
    Array.Sort(arr,a,b);
    return arr[a];
}

 public static int PartSort(int[] arrey, int start, int end)
{
    int len = arrey.Length;
    int variable;
    int result = arrey[start];
    while ( len > 0)
    {
        for (int i = start; i < end; i++)
        {
            if (arrey[i] > arrey[i + 1])
            {
                variable = arrey[i];
                arrey[i] = arrey[i + 1];
                arrey[i+1] = variable;
            }
        }
        len --;
    }
    return Array.IndexOf(arrey, result);
}

 static int PartSort(int[] arr, int lcr, int rcr){
    int val = arr[lcr];
    int[] arr2 = new int[rcr-lcr+1];
    for(int  i = 0; i<= rcr-lcr; i++){
        arr2[i] = arr[lcr+i];
    }
    Array.Sort(arr2);
    for(int i = 0; i< arr2.Length; i++){
        if(arr2[i] == val) return i;
    }
    return 0;
}