Partition

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

Najważniejszą częścią algorytmu Quicksort jest procedura Partition(A, p, r), która wyznacza indeks q taki, że każdy element podtablicy A[p..q-1] jest mniejszy lub równy elementowi A[q], który z kolei jest mniejszy lub równy każdemu elementowi podtablicy A[q+1..r].

Twoim zadaniem jest wczytanie $n$ liczb do tablicy A i wykonanie procedury Partition na tej tablicy w oparciu o następujący pseudokod:

// 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
         i = i+1
         swap A[i] with A[j] 
  swap A[i+1] with A[r]
  return i+1    

Wejście

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

Wyjście

Pierwszy wiersz wyjścia zawiara ciąg $n$ elementów $a_i$ w takiej kolejności, w jakiej znajdą się one po wykonaniu procedury Partition. Element o indeksie $q$ wypisz w nawiasach kwadratowych.

Ograniczenia

• $1 \le n \le 100000$
• $-10^9 \le a_i \le 10^9$

Przykłady

Wejście 1

12
13 19 9 5 12 8 7 4 21 2 6 11

Wyjście 1

9 5 8 7 4 2 6 [11] 21 13 19 12