import java.util.Random;


public class QuickSort {

    //Podajemy rozmiar listy
    private static int rozmiarListy=10000;

    //Podajemy typ wypelnienia listy
    // l-losowo m-malejąco

    private static char typWypelnienia='l';

    private static int dolnyZakresLosowania=1;
    private static int gornyZakresLosowania=10000;



    private static Integer[] listaSortowania=new Integer[rozmiarListy];

    static int liczbaOperacji=0;


    public static void main(String[] args) {

        if (typWypelnienia == 'l') {
            losoweWypelnienieListy();
        } else if (typWypelnienia == 'm') {
            malejaceWypelnienieListy();
        }

        quickSort(0,rozmiarListy-1);
        //wypiszListe();

        System.out.println(liczbaOperacji);


    }


    private static void quickSort(int poczatekPrzedzialu, int koniecPrzedzialu){

        int j=poczatekPrzedzialu;

        for (int i=poczatekPrzedzialu; i<koniecPrzedzialu; i++ ){

            if (listaSortowania[i]<=listaSortowania[koniecPrzedzialu]){
                zamienMiejscami(i,j);
                j++;

            }

        }

        if (poczatekPrzedzialu<koniecPrzedzialu) {

            zamienMiejscami(j, koniecPrzedzialu);
            quickSort(poczatekPrzedzialu, j-1);
            quickSort(j+1, koniecPrzedzialu);

        }

    }


    private static void zamienMiejscami(int indeks1, int indeks2){

        liczbaOperacji++;

        int zmiennaPetli=listaSortowania[indeks1];
        listaSortowania[indeks1]=listaSortowania[indeks2];
        listaSortowania[indeks2]=zmiennaPetli;

    }


    private static void wypiszListe(){
        for (int i=0;i<rozmiarListy;i++)
            System.out.print(listaSortowania[i]+" , ");

        System.out.println("");
        System.out.println("");

    }


    private static void losoweWypelnienieListy(){
        Random random = new Random();

        for (int i=0;i<rozmiarListy;i++)
            listaSortowania[i]=(random.nextInt(gornyZakresLosowania - dolnyZakresLosowania + 1) + dolnyZakresLosowania );

        //wypiszListe();

    }


    private static void malejaceWypelnienieListy(){

        for (int i=0;i<rozmiarListy;i++)
            listaSortowania[i]=rozmiarListy-i;

        //wypiszListe();

    }


}