//三向切分的快速排序

 //这种切分方法对于数组中有大量重复元素的情况有比较大的性能提升

 public static void main(String[] args)

 {

     Scanner input = new Scanner(System.in);

     int n = input.nextInt();

     int[] a = new int[n];

     for(int i = 0; i < a.length; i++)

     a[i] = (int)(Math.random() * 100);

     //System.out.println(Arrays.toString(a));

     long start = System.currentTimeMillis();

     qsort3way(a, 0, a.length - 1);

     long end = System.currentTimeMillis();

     //System.out.println(Arrays.toString(a));

     System.out.println(end - start);

     //10000000个测试数据用时350ms 相比普通快速排序提升约35%的性能

 }    

 public static void qsort3way(int[] a, int front, int rear)

 {

     if(front >= rear)

     return;

     int key_index = front, i = front + 1, j = rear;

     while(i <= j)

     {

     if(a[i] < a[key_index])   //key_index永远指向第一个key值

         swap(a, i++, key_index++);

     else if(a[i] > a[key_index])

         swap(a, i, j--);

     else   //a[i] = a[key_index]

         i++;

     }

     qsort3way(a, front, key_index - 1);

     qsort3way(a, j + 1, rear);

 }