Quick sort is based on the Divide-and-conquer approach. In QuickSort(A, p, r), first, a procedure Partition(A, p, r) divides an array A[p..r] into two subarrays A[p..q-1] and A[q+1..r] such that each element of A[p..q-1] is less than or equal to A[q], which is, inturn, less than or equal to each element of A[q+1..r]. It also computes the index q.

In the conquer processes, the two subarrays A[p..q-1] and A[q+1..r] are sorted by recursive calls of QuickSort(A, p, q-1) and QuickSort(A, q+1, r).

Your task is to read a sequence A and perform the Partition based on the following pseudocode:


Partition(A, p, r)
1 x = A[r]
2 i = p-1
3 for j = p to r-1
4     do if A[j] <= x
5        then i = i+1
6            exchange A[i] and A[j]
7 exchange A[i+1] and A[r]
8 return i+1


Note that, in this algorithm, Partition always selects an element A[r] as a pivot element around which to partition the array A[p..r].

Constraints

* 1 ≤ n ≤ 100,000
* 0 ≤ Ai ≤ 100,000

Input

The first line of the input includes an integer n, the number of elements in the sequence A.

In the second line, Ai (i = 1,2,...,n), elements of the sequence are given separated by space characters.

Output

Print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character. The element which is selected as the pivot of the partition should be indicated by [  ].

Example

Input

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


Output

9 5 8 7 4 2 6 [11] 21 13 19 12
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO ?????????????????????????????????????????????
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = 0;
		int tmp = br.read();
		while(tmp != 13 && tmp != 10){
			n = n * 10 + (tmp - '0');
			tmp = br.read();
		}

		int[] array = new int[n];
		int num = 0;
		int i1 = 0;
		tmp = br.read();
		if(tmp == 13 || tmp == 10){
			tmp = br.read();
		}
		while(tmp != -1 && tmp != 10 && tmp != 13){
			num = 0;
			while(tmp >= '0' && tmp <= '9'){
				num = num * 10 + (tmp - '0');
				tmp = br.read();
			}
			if(tmp == -1){
				break;
			}
			array[i1] = num;
			i1++;
			tmp = br.read();
		}
		
		int index = partition(array, 0, array.length - 1);
		StringBuilder sb = new StringBuilder();
		int outLen = array.length;
		
		if(index != 0){
			sb.append(array[0]);
		}
		else{
			sb.append("["+array[0] + "]");
		}
		for(int i = 1; i < outLen ; i++){
			//sb.append(" "+array[i]);
			if(i == index){
				sb.append(" ["+array[i] + "]");
				
			}
			else{
				sb.append(" "+array[i]);
				
			}
		}
		System.out.println(sb);
	}
	
	static int partition(int[] array, int p, int r){
		int x = array[r];
		int i = p - 1;
		for(int j = p ; j <= r -1 ;j++){
			if(array[j] <= x){
				i++;
				int tmp = array[i];
				array[i] = array[j];
				array[j] = tmp;
				
			}
		}
		int tmp = array[i + 1];
		array[i + 1] = array[r];
		array[r] = tmp;
		return i + 1;
	}

}