#include <iostream>
#include <vector>
#include <algorithm>




int partition(int *lista, int l, int r){
    int p = median_of_three(lista,l,r);
    while(l<r){
        if (lista[l] < lista[p])
            l++;
        else if (lista[r] > lista[p])
            r++;
        else
            swap (lista[r]m lista[l]);
    }
    if (lista[l] < list[p])
        l++;
    swap(lista[l], lista[p]);
    return l;
}

void quicksort (int *lista, int l, int r){
    if (r-1 < l)
        return;
    int piv = partition(lista, l, r);
    quicksort(lista, l, piv-1);
    quicksort(lista, piv+1, r);
}

int median_of_three(int *list, int left, int right){
    int middle = (left+right)/2;

    if (list[middle] < list[left])
        swap(list[right], list[middle]);
    if (list[right] < list[left])
        swap(list[left], list[right]);
    if (list[right] < list[middle])
        swap(list[middle], list[right]);
    return right;
}