Partition

partition ( A, p, r )は、配列 A[ p..r ] を A[ p..q − 1] の各要素が A[q] 以下で、A[ q +1.. r ] の各要素が A[ q ] より大きい A[ p..q − 1] と A[q + 1..r ] に分割し、インデックス q を戻り値として返します。

数列 $A$ を読み込み、次の疑似コードに基づいた partition を行うプログラムを作成してください。

1 partition(A, p, r)
2   x = A[r]
3   i = p-1
4   for j = p to r-1
4     if A[j] <= x
5       i = i+1
6       A[i] と A[j] を交換
7   A[i+1] と A[r] を交換
8   return i+1

ここで、$r$ は配列 $A$ の最後の要素を指す添え字で、$A[r]$ を基準として配列を分割することに注意してください。

入力

入力の最初の行に、数列 $A$ の長さを表す整数 $n$ が与えられます。２行目に、$n$ 個の整数 $A_i$ ($i=1,2,...,n$) が空白区切りで与えられます。

出力

分割された数列を1行に出力してください。数列の連続する要素は１つの空白で区切って出力してください。また、partition の基準となる要素を [   ]で示してください。

制約

• $1 \leq n \leq 100,000$
• $0 \leq A_i \leq 100,000$

入力例 1

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

出力例 1

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

Note

Algorithm

 

---