The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with a running time of $unrecognized$. In these next few challenges, we're covering a divide-and-conquer algorithm called Quicksort (also known as Partition Sort).  This challenge is a modified version of the algorithm that only addresses partitioning.  It is implemented as follows: 

Step 1: Divide 

Choose some pivot element, $unrecognized$, and partition your unsorted array, $unrecognized$, into three smaller arrays: $unrecognized$, $unrecognized$, and $unrecognized$, where each element in $unrecognized$, each element in $unrecognized$, and each element in $unrecognized$. 

Example 

$unrecognized$   

In this challenge, the pivot will always be at $unrecognized$, so the pivot is $unrecognized$.

$unrecognized$ is divided into $unrecognized$, $unrecognized$, and $unrecognized$. 

Putting them all together, you get $unrecognized$. There is a flexible checker that allows the elements of $unrecognized$ and $unrecognized$ to be in any order.  For example, $unrecognized$ is valid as well.    

Given $unrecognized$ and $unrecognized$, partition $unrecognized$ into $unrecognized$, $unrecognized$, and $unrecognized$ using the Divide instructions above. Return a 1-dimensional array containing each element in $unrecognized$ first, followed by each element in $unrecognized$, followed by each element in $unrecognized$.   

Function Description  

Complete the quickSort function in the editor below.     

quickSort has the following parameter(s):  

int arr[n]: $unrecognized$ is the pivot element    

Returns   

int[n]: an array of integers as described above   

Input Format

The first line contains $unrecognized$, the size of $unrecognized$. 

The second line contains $unrecognized$ space-separated integers $unrecognized$ (the unsorted array). The first integer, $unrecognized$, is the pivot element, $unrecognized$.

Constraints

$unrecognized$   
$unrecognized$ where $unrecognized$   
All elements are distinct.

Sample Input
STDIN       Function
-----       --------
5           arr[] size n =5
4 5 3 7 2   arr =[4, 5, 3, 7, 2]

Sample Output
3 2 4 5 7

Explanation

$unrecognized$ 
Pivot: $unrecognized$. 

$unrecognized$; $unrecognized$; $unrecognized$

$unrecognized$, so it is added to $unrecognized$. 

$unrecognized$; $unrecognized$; $unrecognized$

$unrecognized$, so it is added to $unrecognized$. 

$unrecognized$; $unrecognized$; $unrecognized$

$unrecognized$, so it is added to $unrecognized$. 

$unrecognized$; $unrecognized$; $unrecognized$

$unrecognized$, so it is added to $unrecognized$. 

$unrecognized$; $unrecognized$; $unrecognized$

Return the array $unrecognized$.

The order of the elements to the left and right of $unrecognized$ does not need to match this answer.  It is only required that $unrecognized$ and $unrecognized$ are to the left of $unrecognized$, and $unrecognized$ and $unrecognized$ are to the right.

Source: hackerrank | Difficulty: EASY
Tags: Sorting


Solutions:
size = int(input())
array = input().split(' ')
arr = ['None'] * size
for i in range(size):
	arr[i] = int(array[i])
p = arr[0]
less = []
more = []
for i in range(size):
	if arr[i] < p:
		less.append(arr[i])
	else:
		more.append(arr[i])
for j in range(len(less)):
	print(less[j], end=' ')
for k in range(len(more)):
	print(more[k], end=' ')


n = int(input())
lst = list(map(int, input().split()))
p = lst[0]
bottom = []
top = []

def list_print(lst):
	print(' '.join(map(str, lst)))
for i in lst[1:]:
	if i < p:
		bottom.append(i)
	else:
		top.append(i)
print(' '.join(map(str, bottom + [p] + top)))


n = int(input())
array = [int(x) for x in input().split()]
tmp_array = []
pivot = array[0]
for x in array[1:]:
	if x < pivot:
		tmp_array.append(x)
tmp_array.append(pivot)
for x in array[1:]:
	if x >= pivot:
		tmp_array.append(x)
print(' '.join([str(x) for x in tmp_array]))


n = int(input())
d = [int(x) for x in input().split()]
p = d.pop(0)
l = []
r = []
for x in d:
	if x < p:
		l.append(x)
	else:
		r.append(x)
s = str(l + [p] + r)[1:-1].replace(',', '')
print(s)


def partition(ar):
	p = ar[0]
	left = []
	right = []
	for e in ar[1:]:
		if e <= p:
			left.append(e)
		else:
			right.append(e)
	left.append(p)
	for e in right:
		left.append(e)
	ar[:] = left[:]
	for e in ar:
		print(e, end=' ')
m = input()
ar = [int(i) for i in input().strip().split()]
partition(ar)


import sys
count = None
a_list = []
for line in sys.stdin:
	if count is None:
		count = int(line.strip())
		continue
	a_list = [int(i) for i in line.strip().split(' ')]
p = a_list[0]
smaller_list = []
greater_list = []
for i in a_list[1:]:
	if i >= p:
		greater_list.append(i)
	else:
		smaller_list.append(i)
print(' '.join([str(i) for i in smaller_list + [p] + greater_list]))


def partition(ar):
	less = [x for x in ar if x < ar[0]]
	greater = [x for x in ar if x >= ar[0]]
	less[len(less):] = greater
	print(''.join((c for c in str(less) if c not in '[,]')))
m = input()
ar = [int(i) for i in input().strip().split()]
partition(ar)


def partition(ar):
	p = int(ar[0])
	greater = []
	less = []
	for e in ar[1:]:
		e = int(e)
		if e > p:
			greater.append(e)
		elif e < p:
			less.append(e)
	print(str(less + [p] + greater).replace('[', '').replace(']', '').replace(',', ''))
p = input()
ar = input()
partition(ar.split())


def partition(ar):
	p = ar.pop(0)
	rt = [i for i in ar if i <= p] + [p] + [i for i in ar if i > p]
	return ' '.join([str(i) for i in rt])
m = int(input())
ar = [int(i) for i in input().strip().split()]
print(partition(ar))


def quickSort(m, ar):
	if m < 2:
		print(ar[0])
	else:
		p = ar[0]
		less = []
		more = []
		for item in ar[1:]:
			if item < p:
				less.append(item)
			else:
				more.append(item)
		final = less + [p] + more
		print(' '.join([str(x) for x in final]))
m = int(input())
ar = [int(i) for i in input().strip().split()]
quickSort(m, ar)


s = input()
ar = input()

def method_partition(ar):
	ar = ar.split()
	p = ar[0]
	p_less = []
	p_more = []
	for num in ar:
		if int(num) < int(p):
			p_less.append(num)
		if int(num) > int(p):
			p_more.append(num)
	ar = p_less + [p] + p_more
	return ' '.join(ar)
print(method_partition(ar))


num = input()
(pivot, *ar) = input().split()
left = [x for x in ar if int(x) <= int(pivot)]
right = [x for x in ar if int(x) > int(pivot)]
print(' '.join(left + [pivot] + right))


def partition(ar):
	lessarr = []
	morearr = []
	n = len(ar)
	v = ar[0]
	for i in range(0, n):
		if ar[i] < v:
			lessarr.append(ar[i])
		else:
			morearr.append(ar[i])
	for x in morearr:
		lessarr.append(x)
	return lessarr
n = int(input(''))
elem = input('')
numbers = elem.split()
arr = []
for i in range(0, n):
	arr.append(int(numbers[i]))
arr = partition(arr)
for x in arr:
	print(x, end=' ')
print('')


l = int(input())
ar = input().split()
p = int(ar[0])
o = [p]
if l == 1:
	print(a[0])
left = []
right = []
i = 1
j = l - 1
while i <= j:
	while i < l and int(ar[i]) <= p:
		i += 1
		if i - 1 <= j:
			left.append(ar[i - 1])
	while j > 0 and int(ar[j]) >= p:
		j -= 1
		if i <= j + 1:
			right.insert(0, ar[j + 1])
	if i < j:
		o.insert(0, ar[j])
		o.append(ar[i])
		i += 1
		j -= 1
if len(left) > 0:
	left = left + o
	o = left
if len(right) > 0:
	o += right
for num in o:
	print(num, end=' ')
print()


l = int(input())
ar = input().split()
first = []
second = []
fin = []
for i in range(l):
	ar[i] = int(ar[i])
p = ar[0]
for k in range(1, l):
	if ar[k] < p:
		first.append(ar[k])
	else:
		second.append(ar[k])
fin = fin + first
fin.append(ar[0])
fin = fin + second
string = ''
for m in range(l):
	string = string + str(fin[m]) + ' '
print(string)


def partition(li):
	if len(li) <= 1:
		return li
	pivot = li[0]
	lesser = [x for x in li[1:] if x < pivot]
	greater = [x for x in li[1:] if x >= pivot]
	return lesser + [pivot] + greater
n = input()
array = [int(x) for x in input().split()]
print(' '.join(map(str, partition(array))))


def partition(elements):
	pivot = elements[0]
	left = []
	right = []
	for element in elements:
		if element < pivot:
			left.append(element)
		else:
			right.append(element)
	return left + right
n = [int(i) for i in input().strip().split()]
elements = [int(j) for j in input().strip().split()]
print(*partition(elements))


import sys

def print_ar(a):
	for i in a:
		print(i, end=' ')
	print('')
n = int(sys.stdin.readline())
raw = sys.stdin.readline().split()
ar = []
left = []
right = []
final = []
for i in raw:
	ar.append(int(i))
pivot = ar[0]
for i in range(1, n):
	if ar[i] > pivot:
		right.append(ar[i])
	else:
		left.append(ar[i])
for i in left:
	final.append(i)
final.append(pivot)
for i in right:
	final.append(i)
print_ar(final)


def partition(ar):
	print(' '.join(map(str, [i for i in ar if i < ar[0]] + [ar[0]] + [i for i in ar if i > ar[0]])))
m = input()
ar = [int(i) for i in input().strip().split()]
partition(ar)


def printArray(arr):
	s = ''
	for i in range(0, len(arr)):
		s = s + repr(arr[i]) + ' '
	print(s.strip())

def Quicksort1(arr):
	v = arr[0]
	small = []
	big = []
	for i in range(1, len(arr)):
		if arr[i] < v:
			small.append(arr[i])
		else:
			big.append(arr[i])
	arr = small + [v] + big
	printArray(arr)
m = int(input())
arr = []
temp = input().strip().split()
for i in temp:
	arr.append(int(i))
Quicksort1(arr)


def main():
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	p = arr[0]
	l = [x for x in arr if x < p]
	r = [x for x in arr if x > p]
	x = l + [p] + r
	for i in x:
		print(i, end=' ')
main()


import sys

def partition(ar):
	return [n for n in ar if n < ar[0]] + [n for n in ar if n >= ar[0]]
n = int(sys.stdin.readline())
ar = list(map(int, sys.stdin.readline().split()))
print(' '.join(map(str, partition(ar))))


import copy

def printArrayAsString(arToPrint):
	arStringInt = []
	for i in arToPrint:
		arStringInt.append(str(i))
	print(' '.join(arStringInt))

def insertSort(arIntToSort):
	numOcurence = 0
	for index in range(1, len(arIntToSort)):
		valueToInsert = arIntToSort[index]
		holePos = index
		while holePos > 0 and valueToInsert < arIntToSort[holePos - 1]:
			arIntToSort[holePos] = arIntToSort[holePos - 1]
			holePos = holePos - 1
			numOcurence = numOcurence + 1
		arIntToSort[holePos] = valueToInsert
	return numOcurence

def quickSort(arToQuickSort):
	arToProcessLeft = []
	arToProcessRight = []
	p = arToQuickSort[0]
	for index in range(1, len(arToQuickSort)):
		if arToQuickSort[index] >= p:
			arToProcessRight.append(arToQuickSort[index])
			continue
		if arToQuickSort[index] < p:
			arToProcessLeft.append(arToQuickSort[index])
			continue
	return arToProcessLeft + [p] + arToProcessRight

def main():
	strLengthArray = input()
	intLengthArray = int(strLengthArray)
	strValidArray = input()
	arStringValidArray = strValidArray.split()
	arIntValidArray = []
	for val in arStringValidArray:
		arIntValidArray.append(int(val))
	printArrayAsString(quickSort(arIntValidArray))
main()


def start():
	n = int(input())
	text = input().split(' ')
	a = []
	for i in range(n):
		a.append(int(text[i]))
	return (a[0], a[1:])

def printArray(a):
	n = len(a) - 1
	for i in range(n):
		print(a[i], ' ', sep='', end='')
	print(a[n])

def partitionSort(a, p):
	n = len(a)
	b = []
	c = []
	for i in range(n):
		if a[i] < p:
			b.append(a[i])
		else:
			c.append(a[i])
	b.append(p)
	for num in c:
		b.append(num)
	return b
inputs = start()
printArray(partitionSort(inputs[1], inputs[0]))


N = int(input())
ar = [int(x) for x in input().strip().split(' ')]
(p, L, R) = (ar[0], [], [])
for i in ar:
	if i < p:
		L.append(i)
	if i > p:
		R.append(i)
result = L + [p] + R
s = ''
for i in result:
	s += ' ' + str(i)
print(s[1:])


def partition(ar):
	pivot = ar[0]
	arless = []
	armore = []
	for j in range(1, len(ar)):
		if ar[j] < pivot:
			arless.append(ar[j])
		elif ar[j] > pivot:
			armore.append(ar[j])
	ar = arless + [pivot] + armore
	print(' '.join(map(str, ar)))
	return ''
m = input()
ar = [int(i) for i in input().strip().split()]
partition(ar)


n = input()
ar = input().split()
p = ar[0]
l = []
r = []
for i in ar:
	if int(p) > int(i):
		l.append(i)
	elif p == i:
		pass
	else:
		r.append(i)
print(' '.join(l + [p] + r))


def main():
	N = int(input())
	arr = list(map(int, str(input()).split()))
	left = []
	right = []
	p = arr[0]
	for i in arr:
		if i > p:
			right.append(i)
		elif i < p:
			left.append(i)
	if len(left) > 0 and len(right) > 0:
		print(' '.join(map(str, left)) + ' ' + str(p) + ' ' + ' '.join(map(str, right)))
	elif len(left) > 0:
		print(' '.join(map(str, left)) + ' ' + str(p))
	elif len(right) > 0:
		print(str(p) + ' ' + ' '.join(map(str, right)))
	else:
		print(p)
main()


N = int(input())
IN = input()
A = IN.split(' ')
less = []
greater = []
for i in range(1, N):
	if int(A[i]) <= int(A[0]):
		less.append(int(A[i]))
	else:
		greater.append(int(A[i]))
less.append(A[0])
for a in greater:
	less.append(a)
for i in range(0, len(less)):
	print(less[i], end=' ')


def partition(a, n):
	i = 0
	pivot = a[0]
	b = []
	for j in range(1, n):
		if a[j] > pivot:
			b.append(a[j])
		else:
			b.insert(i, a[j])
			i = i + 1
	b.insert(i, pivot)
	return b
n = int(input())
array = list(map(int, input().split()))
result = partition(array, n)
print(' '.join(map(str, result)))


def partition(ar):
	first = ar[0]
	left = []
	right = []
	for i in range(1, len(ar)):
		if ar[i] < first:
			left.append(ar[i])
		else:
			right.append(ar[i])
	left.append(first)
	left.extend(right)
	print(' '.join((str(n) for n in left)))
	return ''
m = input()
ar = [int(i) for i in input().strip().split()]
partition(ar)


def main():
	size = int(input())
	arr_str = input()
	arr = list(map(int, arr_str.split()))
	p = arr[0]
	x = []
	y = []
	for item in arr:
		if item < p:
			x.append(item)
		elif item > p:
			y.append(item)
	ret_str = ' '.join((str(e) for e in x))
	ret_str = ret_str + ' ' + str(p) + ' '
	ret_str += ' '.join((str(e) for e in y))
	print(ret_str)
main()


number = int(input())
list = input().split(' ')
left = []
right = []
comp = int(list[0])
for element in list:
	try:
		if int(element) < comp:
			left.append(element)
		else:
			right.append(element)
	except:
		continue
for element in left + right:
	print(element, end=' ')


def printArr(arr):
	for elt in arr:
		print(elt, end=' ')
n = int(input())
args = [int(i) for i in input().split()]
p = args[0]
right = []
left = []
for i in range(1, len(args)):
	if args[i] < p:
		left.append(args[i])
	else:
		right.append(args[i])
printArr(left)
print(p, end=' ')
printArr(right)


def quick_sort(l):
	less = []
	greater = []
	pivot = l[0]
	for x in l[1:]:
		if x < pivot:
			less.append(x)
		else:
			greater.append(x)
	return less + [pivot] + greater
size = input()
data = [int(x) for x in input().strip().split(' ')]
result = ' '.join((str(x) for x in quick_sort(data)))
print(result)


n = int(input())
st = input().strip().split()
p = int(st[0])
ar = [int(i) for i in st[1:]]
s = [e for e in ar if e < p]
d = [e for e in ar if e > p]
ans = s + [p] + d
print(*ans, sep=' ')


n = int(input())
ar = [int(x) for x in input().split()]
p = ar[0]
if n == 1:
	print(str(p))
else:
	p_count = 1
	left = []
	right = []
	for number in ar[1:]:
		if number < p:
			left.append(number)
		elif number > p:
			right.append(number)
		else:
			p_count += 1
	result = left + [p] * p_count + right
	print(' '.join(map(str, result)))


input()
nums = list(map(int, input().split()))

def quicksort(nums):
	pivot = nums[0]
	lt = []
	gt = []
	for num in nums[1:]:
		if num < pivot:
			lt.append(num)
		else:
			gt.append(num)
	return lt + [pivot] + gt
print(' '.join(map(str, quicksort(nums))))


def partition(ar):
	final = []
	p = ar[0]
	n1 = []
	n2 = []
	for x in ar[1:]:
		if x < p:
			n1.append(x)
		else:
			n2.append(x)
	final.extend(n1)
	final.append(p)
	final.extend(n2)
	print(*final)
	return ''
m = input()
ar = [int(i) for i in input().strip().split()]
partition(ar)


def quicksort(l):
	p = l[0]
	lower = []
	higher = []
	for x in range(1, len(l)):
		if int(l[x]) < p:
			lower.append(int(l[x]))
		elif int(l[x]) > p:
			higher.append(int(l[x]))
	lower.append(p)
	sorted = str(lower + higher).strip('[]').replace(',', '')
	return sorted
num = input()
l = list(map(int, input().strip().split(' ')))
print(quicksort(l))


def print_array(ar):
	result = ''
	for el in ar:
		result += str(el) + ' '
	result += ''
	print(result)

def partition(ar):
	p = ar[0]
	smaller = []
	bigger = []
	for e in ar:
		if e < p:
			smaller.append(e)
		else:
			bigger.append(e)
	for i in range(len(ar)):
		if i < len(smaller):
			ar[i] = smaller[i]
		elif p not in ar:
			ar[i] = p
		else:
			ar[i] = bigger[i - len(ar)]
	print_array(ar)
m = input()
ar = [int(i) for i in input().strip().split()]
partition(ar)


n = int(input())
s = input().strip().split()
ar = [int(i) for i in s]
s = []
l = []
piv = ar[0]
for i in range(1, n):
	if ar[i] < piv:
		s.append(ar[i])
	else:
		l.append(ar[i])
ar = s + [ar[0]] + l
for i in ar:
	print(i, end=' ')


n = int(input())
a = [int(num) for num in input().split()]
p = a[0]
smaller = []
bigger = []
for i in range(n):
	if a[i] >= p:
		bigger.append(a[i])
	if a[i] < p:
		smaller.append(a[i])
a = smaller + bigger
for i in a:
	print(i, end=' ')


test_input = [('5\n4 5 3 7 2', '3 2 4 5 7')]

def debug(data):
	__builtins__.print(data)

def p(ar):
	text = ' '.join(map(str, ar))
	print(text)

def main():
	from bisect import bisect
	input()
	ar = [int(i) for i in input().split()]
	v = ar[0]
	ar = ar[1:]
	left_ar = []
	right_ar = []
	for i in range(len(ar)):
		if ar[i] < v:
			left_ar.append(ar[i])
		else:
			right_ar.append(ar[i])
	left_ar.append(v)
	ar = left_ar + right_ar
	p(ar)

def test():
	log = []
	global print

	def print(*args, **kwargs):
		log.append(' '.join((str(elem) for elem in args)))
	global input

	def input(idx=None, generator=[None, -1]):
		if idx is not None:
			generator[0] = test_input[idx][0].split('\n')
			generator[1] = -1
			return
		generator[1] += 1
		if generator[1] < len(generator[0]):
			return generator[0][generator[1]]
		return ''
	for (idx, entry) in enumerate(test_input):
		log = []
		input(idx)
		main()
		if '\n'.join(log) == entry[1]:
			__builtins__.print('TEST', idx, ': PASSED')
		else:
			__builtins__.print('TEST', idx, ': FAILED')
main()


length = input()
array = [int(x) for x in input().split()]
pivot = array[0]
left = []
right = []
for i in range(1, len(array)):
	if array[i] < pivot:
		left.append(array[i])
	else:
		right.append(array[i])
print(' '.join(map(str, left + [pivot] + right)))


def partition(L):
	return [a for a in L[1:] if a <= L[0]] + [L[0]] + [a for a in L[1:] if a >= L[0]]
n = int(input())
L = [int(s) for s in input().split()]
print(' '.join([str(s) for s in partition(L)]))


import sys

def is_number(s):
	try:
		float(s)
		return True
	except ValueError:
		pass
	return False

def partition(array, pivot_val):
	left = []
	right = []
	pivot_vals = []
	for i in range(0, len(array)):
		if array[i] > pivot_val:
			right.append(array[i])
		elif array[i] < pivot_val:
			left.append(array[i])
		else:
			pivot_vals.append(array[i])
	return left + pivot_vals + right

def array_to_str(array):
	temp = ''
	for x in range(0, len(array)):
		temp += str(array[x])
		if x + 1 < len(array):
			temp += ' '
	return temp
arr_size = int(sys.stdin.readline())
input_arr = sys.stdin.readline().strip('\n').split(' ')
array = []
found_blank = False
for x in range(0, len(input_arr)):
	if is_number(input_arr[x]):
		array.append(int(input_arr[x]))
	else:
		found_blank = True
pivot_val = array[0]
p_array = partition(array, pivot_val)
out_str = array_to_str(p_array)
if found_blank:
	out_str += ' '
print(out_str)


import sys
numberOfElements = int(sys.stdin.readline())
elements = []
raw = sys.stdin.readline().split()
for index in range(numberOfElements):
	elements.append(int(raw[index]))
p = elements[0]
left = []
middle = []
right = []
for element in elements:
	if element < p:
		left.append(element)
	elif element == p:
		middle.append(element)
	else:
		right.append(element)
for element in left + middle + right:
	print(repr(element), end=' ')


n = int(input())
ar = list(map(int, input().split()))
p = ar[0]
left = []
right = [p]
for x in ar[1:]:
	if x < p:
		left.append(x)
	else:
		right.append(x)
print(' '.join(map(str, left + right)))


x = int(input())
z = input().split()
z1 = []
z2 = []
for i in z:
	if int(i) < int(z[0]):
		z1.append(i)
	else:
		z2.append(i)
z = z1 + z2
x = []
for i in z:
	i = int(i)
	x.append(i)
print(' '.join([str(j) for j in x]))


n = int(input())
array = [int(val) for val in input().split()]
p = array[0]
smaller = []
larger = []
for item in array:
	if item < p:
		smaller += [item]
	elif item > p:
		larger += [item]
[print(val, end=' ') for val in smaller]
print(p, end=' ')
[print(val, end=' ') for val in larger]
print()


size = int(input())
pns = list(map(int, input().split()))
p = pns[0]
ns = pns[1:]
(larges, smalls) = ([], [])
for n in ns:
	if n < p:
		smalls.append(n)
	else:
		larges.append(n)
smalls.append(p)
print(*smalls + larges)


n = int(input())
ar = [int(v) for v in input().split()]
l = 0
for i in range(1, n):
	if ar[i] >= ar[l]:
		continue
	for j in range(i, l, -1):
		(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])
	l += 1
print(' '.join([str(v) for v in ar]))


def partition(ar):
	target = ar[0]
	lower = []
	upper = []
	for x in ar:
		if x < target:
			lower.append(x)
		elif x > target:
			upper.append(x)
	new_ar = [n for n in lower]
	new_ar.append(target)
	new_ar.extend(upper)
	print(' '.join((str(n) for n in new_ar)))
n = input()
ar = [int(i) for i in input().strip().split()]
partition(ar)


import sys

def mToString(mArray):
	startStr = ''
	for el in mArray:
		startStr = startStr + str(el) + ' '
	return startStr[:-1]
lines = []
for line in sys.stdin:
	lines.append(line)
n = int(lines[0])
ar = list(map(int, lines[1].split()))
v = ar[0]
ar = ar[1:]
ar1 = []
ar2 = []
for el in ar:
	if el <= v:
		ar1.append(el)
	else:
		ar2.append(el)
print(mToString(ar1 + [v] + ar2))


n = int(input().strip())
ar = list(map(int, input().strip().split()))
p = ar[0]
left = []
right = []
for v in ar:
	if v < p:
		left.append(v)
	if v > p:
		right.append(v)
print(' '.join(map(str, left + [p] + right)))


import random
n = int(input())
ar = [int(x) for x in input().split()]

def QuickSort(A, start, end):
	global count
	if start < end:
		count += end - start
		pivot_pos = Partition(A, start, end)
		QuickSort(A, start, pivot_pos - 1)
		QuickSort(A, pivot_pos + 1, end)

def Partition(A, start, end):
	pivot = A[0]
	pivot = A.index(pivot)
	(A[start], A[pivot]) = (A[pivot], A[start])
	newPivotIndex = start + 1
	p = A[start]
	for index in range(start + 1, end + 1):
		if A[index] < p:
			(A[newPivotIndex], A[index]) = (A[index], A[newPivotIndex])
			newPivotIndex += 1
	pos = newPivotIndex - 1
	(A[pos], A[start]) = (A[start], A[pos])
	print(A)
	return pos

def partition(A, l, r, pi):
	pV = A[pi]
	(A[pi], A[r]) = (A[r], A[pi])
	storeIndex = l
	for i in range(l, r + 1):
		if A[i] <= pV:
			(A[i], A[storeIndex]) = (A[storeIndex], A[i])
			storeIndex += 1
	print(' '.join(map(str, ar)))

def stablepartition(A):
	pivot = A[0]
	(less, greater) = ([], [])
	for x in A[1:]:
		if x <= pivot:
			less.append(x)
		else:
			greater.append(x)
	final = less + [pivot] + greater
	print(' '.join(map(str, final)))
stablepartition(ar)


n = int(input())
ar = list(map(int, str(input()).split()))
(i, p) = (0, ar[0])
for j in range(1, n):
	if p < ar[j]:
		continue
	v = ar[j]
	for k in range(j, i, -1):
		ar[k] = ar[k - 1]
	ar[i] = v
	i += 1
print(' '.join(map(str, ar)))


s = int(input())
arr = [int(x) for x in input().split()]

def printList(l):
	op = ''
	for a in l:
		op = op + str(a) + ' '
	print(op)
g = []
l = []
for i in range(1, s):
	if arr[i] > arr[0]:
		g.append(arr[i])
	else:
		l.append(arr[i])
printList(l + [arr[0]] + g)


import sys
n = int(sys.stdin.readline().strip())
ar = [int(elem) for elem in sys.stdin.readline().split()]
p = ar[0]
ar_left = []
ar_right = []
for i in range(1, n):
	if ar[i] <= p:
		ar_left.append(ar[i])
	else:
		ar_right.append(ar[i])
ar_left.append(ar[0])
ar = ar_left + ar_right
print(str(ar).strip('[]').replace(',', ''))


N = int(input())
a = tuple((int(s) for s in input().split()))
k = a[0]
b = a[1:]
b = tuple(filter(lambda n: n < k, b)) + (k,) + tuple(filter(lambda n: n >= k, b))
print(str(b)[1:-1].replace(',', ''))


n = int(input().strip())
A = list(map(int, input().strip().split(' ')))

def partition(A, n):
	a = [x for x in A[1:] if x <= A[0]]
	b = [x for x in A[1:] if x > A[0]]
	return a + [A[0]] + b
A = partition(A, n - 1)
print(str(A).replace(',', '')[1:-1])


import sys

def quick_sort(arr, s):
	smaller = []
	bigger = []
	value = arr[0]
	for x in range(1, s):
		if arr[x] >= value:
			bigger.append(arr[x])
		else:
			smaller.append(arr[x])
	result = smaller + [value] + bigger
	result = [str(i) for i in result]
	print(' '.join(result))
size = int(sys.stdin.readline().strip())
array = sys.stdin.readline().strip().split()
array = [int(i) for i in array]
quick_sort(array, size)


input()
ar = [int(i) for i in input().split()]

def part(ar):
	return [l for l in ar[1:] if l <= ar[0]] + [ar[0]] + [r for r in ar if r > ar[0]]
print(' '.join((str(i) for i in part(ar))))


T = int(input())
array = input().split()
newarray = []
for i in range(T):
	if int(array[i]) < int(array[0]):
		newarray.append(array[i])
newarray.append(int(array[0]))
for i in range(T):
	if int(array[i]) > int(array[0]):
		newarray.append(array[i])
print(' '.join((str(x) for x in newarray)))


N = int(input())
ar = [int(e) for e in input().split()]
lt = []
gt = []
p = ar[0]
for a in ar[1:]:
	if a < p:
		lt.append(a)
	else:
		gt.append(a)
ar = lt + [p] + gt
print(' '.join([str(e) for e in ar]))


def printLst(lst):
	for i in lst[:-1]:
		print(i, end=' ')
	print(lst[-1])

def partSort(ar):
	pivot = ar[0]
	lowList = []
	highList = []
	for i in range(1, len(ar)):
		if ar[i] < pivot:
			lowList.append(ar[i])
		else:
			highList.append(ar[i])
	return lowList + [pivot] + highList
input()
ar = [int(x) for x in input().split()]
printLst(partSort(ar))


def print_array(a):
	for elem in a:
		print(elem, end=' ')
n = int(input())
array = list(map(int, input().split()))
pivot = array[0]
list1 = []
list2 = []
list3 = []
for elem in array:
	if elem < pivot:
		list1.append(elem)
	elif elem == pivot:
		list2.append(elem)
	else:
		list3.append(elem)
final = list1 + list2 + list3
print_array(final)


N = int(input())
inp = list(map(int, input().split()))
P = inp[0]
(left, right) = ([], [])
for i in range(1, N):
	if inp[i] < P:
		left.append(inp[i])
	else:
		right.append(inp[i])
output = left + [P] + right
print(' '.join((str(ch) for ch in output)))


size = int(input())
ar = [int(x) for x in input().split()]

def quick_sort(ar):
	left = []
	right = []
	pivot = ar.pop(0)
	for a in ar:
		if a < pivot:
			left.append(a)
		else:
			right.append(a)
	left.append(pivot)
	return left + right
print(' '.join(map(str, quick_sort(ar))))


n = int(input())
ar = list(map(int, input().strip().split()))
p = ar[0]
arl = list()
arr = list()
for i in range(n):
	if ar[i] >= p:
		arr.append(ar[i])
	else:
		arl.append(ar[i])
print(' '.join(map(str, arl + arr)))


num = int(input())
seperate = input().split()
seperate = list(map(int, seperate))
moveOn = seperate[0]
leftSide = []
rightSide = []
for i in range(1, num):
	if seperate[i] < moveOn:
		leftSide.append(seperate[i])
	else:
		rightSide.append(seperate[i])
s = ''
for i in leftSide:
	s += str(i) + ' '
s += str(moveOn) + ' '
for i in rightSide:
	s += str(i) + ' '
print(s)


n = int(input())
a = list(map(int, input().split()))
b = []
c = []
p = a[0]
for i in range(1, len(a)):
	if a[i] > p:
		c.append(a[i])
	else:
		b.append(a[i])
print(' '.join(map(str, b + [p] + c)))


def quickSort(ar, sortby):
	greater = []
	smaller = []
	for i in ar:
		if i > sortby:
			greater.append(i)
		else:
			smaller.append(i)
	return smaller + [sortby] + greater
s = int(input())
ar = [int(i) for i in input().strip().split()]
p = ar.pop(0)
sortedAr = quickSort(ar, p)
print(' '.join((str(i) for i in sortedAr)))


def quicksort_partition(a):
	pivot = a[0]
	(lesser, greater) = ([], [])
	for x in a:
		if x < pivot:
			lesser.append(x)
		else:
			greater.append(x)
	return lesser + greater
n = int(input())
a = [int(x) for x in str(input()).split()]
print(' '.join([str(x) for x in quicksort_partition(a)]))


def partition(numbers):
	pivot = numbers[0]
	list_smaller = []
	list_larger = []
	for i in range(1, len(numbers)):
		if numbers[i] <= pivot:
			list_smaller.append(numbers[i])
		else:
			list_larger.append(numbers[i])
	list_smaller.append(pivot)
	list_smaller.extend(list_larger)
	return list_smaller
num_entries = int(input())
values = list(map(int, input().strip().split()))
p_values = partition(values)
print(str(p_values).replace('[', '').replace(']', '').replace(',', ''))


l = int(input())
a = list(input())
b = []
for x in range(0, l):
	b.append('')
index = 0
for x in range(0, len(a)):
	if a[x] != ' ':
		b[index] += a[x]
	if a[x] == ' ':
		index += 1
for x in range(0, len(b)):
	b[x] = int(b[x])
low = []
high = []
for x in range(1, l):
	if b[x] > b[0]:
		high.append(b[x])
	if b[x] < b[0]:
		low.append(b[x])
low.append(b[0])
print(' '.join(map(str, low + high)))


n = input()
ar = [int(i) for i in input().split()]
p = ar.pop(0)
right = []
left = []
while len(ar) > 0:
	e = ar.pop(0)
	if p > e:
		left.append(str(e))
	else:
		right.append(str(e))
print(' '.join(left + [str(p)] + right))


def tc(n, arr):
	p = arr[0]
	res = []
	for a in arr:
		if a < p:
			res.append(a)
	res.append(p)
	for a in arr:
		if a > p:
			res.append(a)
	print(' '.join([str(x) for x in res]))
n = int(input())
arr = [int(x) for x in input().split()]
tc(n, arr)


def partition(a):
	p = a[0]
	lesser = list(filter(lambda x: x < p, a))
	greater = list(filter(lambda x: x > p, a))
	return lesser + [p] + greater

def makelistsameline(strnos):
	return list(map(lambda x: int(x), strnos.split()))
N = int(input())
L = makelistsameline(input())
print(' '.join(map(str, partition(L))))


def partition(a, p):
	(b, c) = ([], [a.pop(0)])
	for i in a:
		if i < p:
			b.append(i)
		else:
			c.append(i)
	return b + c
n = int(input().strip())
ar = list(map(int, input().strip().split()))
print(' '.join(map(str, partition(ar, ar[0]))))


from sys import stdin
n = int(stdin.readline())
ar = [int(x) for x in stdin.readline().split()]
print(' '.join([str(x) for x in ar if x < ar[0]] + [str(ar[0])] + [str(x) for x in ar if x > ar[0]]))


n = int(input())
nbs = [int(i) for i in input().split()]
p = nbs.pop(0)
l1 = []
l2 = []
for i in nbs:
	if i < p:
		l1.append(i)
	else:
		l2.append(i)
print(' '.join(map(str, l1 + [p] + l2)))


def partition(a, l, r):
	sm = []
	lg = []
	ident = []
	p = a[l]
	for i in range(l, r + 1):
		if l == i:
			continue
		elif a[i] < p:
			sm.append(a[i])
		elif a[i] > p:
			lg.append(a[i])
		else:
			ident.append(a[i])
	sm.extend(ident)
	sm.append(p)
	sm.extend(lg)
	a[l:r + 1] = sm
n = int(input())
a = [int(x) for x in input().strip().split()]
assert n == len(a)
partition(a, 0, len(a) - 1)
print(' '.join(map(str, a)))


input()
nums = list(map(int, input().split()))
part = [n for n in nums[1:] if n <= nums[0]] + [nums[0]] + [n for n in nums[1:] if n > nums[0]]
print(' '.join(map(str, part)))