Quicksort

Limit czasu: 1s | Limit pamięci: 64MB

Dany jest ciąg liczb $a_1, a_2, \ldots, a_n$. Posortuj te elementy za pomocą algorytmu quicksort, tzn. zastosuj poniższy algorytm:

	// Cormen et al. - Introduction to Algorithms
	Partition(A, p, r)
	  x = A[r]
	  i = p-1
	  for j = p to r-1
	      if A[j] <= x   // ILE RAZY WYKONA SIĘ TA INSTRUKCJA?
	         i = i+1
	         swap A[i] with A[j] 
	  swap A[i+1] with A[r]
	  return i+1 

	Quicksort(A, p, r)
	   if p < r
	      q = Partition(A, p, r)
	      Quicksort(A, p, q-1)
	      Quicksort(A, q+1, r)   

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę $n$. Drugi wiersz zawiera $n$ liczb $a_i$.

Wyjście

Pierwszy wiersz wyjścia zawiara posortowany ciąg $n$ elementów $a_i$ w kolejności niemalejącej. W drugim wierszu wypisz ile razy wykona się test A[j] <= x we funkcji Partition.

Ograniczenia

• $1 \le n \le 500 000$
• $-10^9 \le a_i \le 10^9$

Przykłady

Wejście 1

10
8 5 9 2 6 3 7 1 10 4

Wyjście 1

1 2 3 4 5 6 7 8 9 10
21