Problem:
Partition 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 Input The first line of the input includes an integer n , the number of elements in the sequence A. In the second line, A i ( 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 [  ] . Constraints  1 ≤ n ≤ 100,000  0 ≤ A i ≤ 100,000  Sample Input 1 12
13 19 9 5 12 8 7 4 21 2 6 11 Sample Output 1 9 5 8 7 4 2 6 [11] 21 13 19 12

Solution (Python):
def partition(A,p,r):
    x = A[r]
    i = p-1
    for j in xrange(p,r):
        if A[j] <= x:
            i += 1
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
    tmp = A[i+1]
    A[i+1] = A[r]
    A[r] = tmp
    return i+1

def main():
    n = input()
    A = map(int,raw_input().split())
    pos = partition(A,0,n-1)
    A = map(str,A)
    A[pos] = "["+A[pos]+"]"
    print " ".join(A)

if __name__ == '__main__':
    main()

Solution (Python):
def partition(A):
    l = len(A) - 1
    x = A[l]
    i = -1
    for j in range(l):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[l] = A[l], A[i+1]
    return i + 1

n = int(input())
A = [int(x) for x in input().split()]
standard = partition(A)
for i in range(len(A)):
    if i == standard:
        print("[{}]".format(A[i]), end=' ')
    elif i != standard and i != len(A)-1:
        print(A[i], end=' ')
    else:
        print(A[i])

Solution (Python):

def partition(A, p, r):
    x = A[r]
    i = p - 1

    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[j], A[i] = A[i], A[j]

    A[i + 1] , A[r] = A[r], A[i + 1]

    return i + 1

n = int(input())
A = [int(a) for a in input().split()]
edge = partition(A, 0, n - 1)

for (i, a) in enumerate(A):
    if i == edge:
        print("[" + str(a) + "]", end = "")
    else:
        print(a, end = "")

    if i != n - 1:
        print(" ", end = "")

print()

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1


if __name__ == '__main__':
    N = int(input().strip())
    AA = [int(a) for a in input().strip().split()]
    i = partition(AA, 0, N - 1)
    _str = ' '.join([str(a) for a in AA[:i]]) + \
           ' [{}] '.format(AA[i]) + \
            ' '.join([str(a) for a in AA[i+1:]])
    print(_str)

Solution (Python):
def partition(A, p, r):
    x, i = A[r], p-1
    for j in range(p,r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

n = int(input())
A = list(map(int,input().split()))
s = partition(A,0,n-1)
print(*A[:s],end = ' ')
print([A[s]],end = ' ')
print(*A[s+1:])

Solution (Python):
def partition(A,p,r):
    x = A[r]
    i = p 
    j = p+1
    while i < r:
        if A[i] <= x:
            i += 1
            if i == j:
                j += 1
        else:
            while j <= r:
                if A[j] <= x:
                    if j == r:
                        temp = A[j]
                        A[j] = A[i]
                        A[i] = "[{}]".format(temp)
                        i += 1
                        break 
                    temp = A[j]
                    A[j] = A[i]
                    A[i] = temp
                    i += 1
                    break
                else:
                    j += 1
            else:
                i+=1
                break
    return A
    
    
n = int(input())
A = list(map(int,input().split()))
print(*partition(A,0,n-1))

Solution (Python):
def partition(A,p,r):
    x = A[r]
    i = p 
    j = p+1
    while i < r:
        if A[i] <= x:
            i += 1
            if i == j:
                j += 1
        else:
            while j <= r:
                if A[j] <= x:
                    if j == r:
                        temp = A[j]
                        A[j] = A[i]
                        A[i] = "[{}]".format(temp)
                        i += 1
                        i = r
                        break 
                    temp = A[j]
                    A[j] = A[i]
                    A[i] = temp
                    i += 1
                    break
                else:
                    j += 1
    return A
    
    
n = int(input())
A = list(map(int,input().split()))
print(*partition(A,0,n-1))

Solution (Python):
def partition(A,p,r):
    x = A[r]
    i = p
    for j in range(p,r):
        if A[j] <= x:
            A[j],A[i] = A[i],A[j]
            i += 1
    A[r],A[i] = A[i],A[r]
    return i

n = int(input())
A = list(map(int,input().split()))
i = partition(A,0,n-1)
A[i] = "[{}]".format(A[i])
print(*A)

Solution (Python):
def partition(n,a,p,r):
  x = a[r]
  i = p - 1
  
  for j in range(p,r):
    if x >= a[j]:
      i += 1
      a[i],a[j] = a[j],a[i]
      
  a[i+1],a[r] = a[r],a[i+1]
  
  for k in range(i+1):
    print(a[k],end=" ")
    
  print("[{}]".format(x),end=" ")
  
  for k in range(i+2,r):
    print(a[k],end=" ")
    
  print(a[r])

n = int(input())
a = list(map(int,input().split()))
partition(n,a,0,len(a)-1)

Solution (Python):
def partition(A, p, r):
  x = A[r]
  i = p - 1
  for j in range(p, r):
    if A[j] <= x:
      i += 1
      A[i], A[j] = A[j], A[i]
  A[i + 1], A[r] = A[r], A[i + 1]
  return i + 1

N = int(input())
A = list(map(int, input().split()))

q = partition(A, 0, len(A) - 1)
result = []
for i in range(len(A)):
  s = "[" + str(A[i]) + "]" if i == q else str(A[i])
  result.append(s)
print(" ".join(result))

Solution (Python):



def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1


def main():
    n = int(input())
    A = [int(e) for e in input().split()]
    p = 0
    idx = partition(A, p, n - 1)
    A = [str(e) for e in A]
    A[idx] = "[{}]".format(A[idx])
    return " ".join(A)


print(main())

Solution (Python):



def partition(a, p, r):
    x = ns[r]
    i = p - 1
    for j in range(p, r):
        if ns[j] <= x:
            i += 1
            ns[i], ns[j] = ns[j], ns[i]
    ns[i + 1], ns[r] = ns[r], ns[i + 1]
    return i + 1, ns


if __name__ == '__main__':
    n = int(input())
    ns = [int(e) for e in input().split()]
    
    
    r = len(ns) - 1
    idx, ns = partition(ns, 0, r)
    ns = [str(n) for n in ns]
    ns[idx] = '[{}]'.format(ns[idx])
    print(" ".join(ns))

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i = i+1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]

    return i+1

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

k = partition(A, 0, len(A)-1)


for i in range(len(A)):
    if i == k:
        print('['+str(A[i])+']', end=' ')
    elif i == n-1:
        print(A[i])
    else:
        print(A[i], end=' ')

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

n = int(input())
A = list(map(int, input().split()))
i = partition(A, 0, n-1)
A[i] = "["+str(A[i])+"]"
print(*A)

Solution (Python):
def partition(A, p, r):
 x = A[r]
 i  = p-1
 for j in range(p,r):
  if A[j] <= x:
   i += 1
   A[i],A[j] = A[j],A[i]
 A[i+1],A[r] = A[r],A[i+1]
 return i+1

n = int(input())
A = list(map(int, input().split()))
x = A[n-1]
q = partition(A, 0, n-1)
print(" ".join(map(str,A[0:q])) + " [" + str(x) + "] " + " ".join(map(str,A[q+1:n])) )

Solution (Python):
def partition(A, p, r):
  x = A[r]
  i = p - 1
  for j in range(p, r):
    if A[j] <= x:
      i += 1
      A[i], A[j] = A[j], A[i]
  A[i+1], A[r] = A[r], A[i+1]
  return i+1

def main():
  n = int(input())
  A = list(map(int, input().split()))
  q = partition(A, 0, n-1)

  A[q] = "[%d]"%A[q]
  print(" ".join(map(str, A)))

if __name__ == "__main__":
  main()

Solution (Python):
def partition(A, p, r):
   x = A[r]
   i = p-1
   for j in range(p, r):
      if A[j] <= x:
         i = i+1
         A[i],A[j] = A[j],A[i]
   A[i+1],A[r] = A[r],A[i+1]
   return i+1

r = int(input())
A = list(map(int, input().split()))
p = partition(A, 0, r-1)
A = list(map(str, A))
A[p] = "[%s]"%(A[p])
print(" ".join(A))

Solution (Python):


def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i = i+1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

n = int(input())
A = list(map(int, input().split()))
m = partition(A, 0, n-1)
A = list(map(str, A))
A[m] = "[%s]"%(A[m])
print(*A)

Solution (Python):
def main():
    n = input()
    A = map(int,raw_input().split())

    q = partition(A,0,n-1)
    for i in range(n-1):
        if i == q:
            print "[{}]".format(A[q]),
        else:
            print A[i],
    print A[-1]

def partition(A,p,r):
    x = A[r]
    i = p - 1
    for j in range(p,r):
        if A[j] <= x:
            i += 1
            a = A[i]
            A[i] = A[j]
            A[j] = a
    b = A[i+1]
    A[i+1] = A[r]
    A[r] = b
    return i+1

if __name__ == "__main__":
    main()

Solution (Python):
def partition(p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
n = int(input())
A = [int(i) for i in input().split()]
q = partition(0, n - 1)
A[q] = "[%d]"%A[q]
print(*A)

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i = i + 1
            temp = A[i]
            A[i] = A[j]
            A[j] = temp
    temp = A[i+1]
    A[i+1] = A[r]
    A[r] = temp
    return i+1


if __name__ == "__main__":
    n = int(input())
    B = list(map(int, input().split()))
    p = partition(B, 0, n-1)
    print(" ".join(map(str, B[:p])) + " [" + str(B[p]) + "] " + " ".join(map(str, B[p+1:])))

Solution (Python):
def swap(A, i, j):

    x = A[i]
    A[i] = A[j]
    A[j] = x

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            swap(A, i, j)



    A[r] = "[{}]".format(A[r])
    swap(A,i+1, r)
    i += 1
    return i

def main():
    """ ????????? """
    num = int(input().strip())
    A = list(map(int,input().split()))
    partition(A, 0, num-1)
    print(" ".join(map(str,A)))

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

i = partition(A, 0, n-1)
print(' '.join(map(str, A[:i])) + ' [' + str(A[i]) + '] ' + ' '.join(map(str, A[i+1:])))

Solution (Python):
n = int(raw_input())
a = map(int, raw_input().split())
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

x = partition(a, 0, n-1)
for i in range(n):
    if i == x:
        print '[%d]' % a[i],
    elif i == n-1:
        print a[i]
    else:
        print a[i],

Solution (Python):
def partition(A,p,n):
    x=A[n-1]
    i=p-1
    for j in range(n-1):
        if A[j]<=x:
            i+=1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[n-1]=A[n-1],A[i+1]
    
    A[i+1]="[{}]".format(A[i+1])
    
    print(*A)
    

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

partition(A,0,n)

Solution (Python):
def partition(A, p, r):
    x = A[r-1]
    i = p-1

    for j in range(p,r-1):
        if A[j] <= x:
            i = i + 1
            A[i],A[j] = A[j],A[i]

    A[i+1],A[r-1] = A[r-1],A[i+1]

    print("{0} [{1}] {2}".format(" ".join(map(str,A[:i+1])),str(A[i+1])," ".join(map(str,A[i+2:]))))

    return



if __name__ == '__main__':
    cnt = int(input())
    A = list(map(int,input().split()))
    p = 0
    r = len(A)
    partition(A,p,r)

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

n = int(input())
A = list(map(int, input().split()))
q = partition(A, 0, n - 1)
print(" ".join(map(str, A[:q])), "[{0}]".format(A[q]),
      " ".join(map(str, A[q + 1:])))

Solution (Python):
def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def partition(A,p=0, r=None):
    if r is None:
        r = len(A)-1
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j] <= x:
            i += 1
            swap(A,i,j)
    swap(A,i+1,r)
    return i+1

if __name__ == "__main__":
    input()
    A = list(map(int, input().strip().split()))
    k = partition(A)
    B = list(map(str, A))
    B[k] = "[{}]".format(B[k])
    print(" ".join(B))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))

x = a[-1]
i = -1

for j in range(len(a)-1):
    if a[j] <= x:
        i += 1
        a[i], a[j] = a[j], a[i]

a[i + 1], a[n - 1] = "[" + str(a[n - 1]) + "]", a[i + 1]

print(*a)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))

def partition(A,p,r):
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j] <= x:
            i += 1
            A[i],A[j] = A[j],A[i]
    A[i+1],A[r] = A[r],A[i+1]
    return i+1

q = partition(A,0,n-1)
print(*A[:q],end=' ')
print('[{0}]'.format(A[q]),end=' ')
print(*A[q+1:])

Solution (Python):

import sys


def partition(lst, p, r):
    x = lst[r]
    i = p - 1
    for j in range(p, r):
        if lst[j] <= x:
            i += 1
            tmp = lst[i]
            lst[i] = lst[j]
            lst[j] = tmp
    i += 1
    tmp = lst[i]
    lst[i] = lst[r]
    lst[r] = tmp
    return i


if __name__ == "__main__":
    data = [val.split() for val in sys.stdin.readlines()]
    n = int(data[0][0])
    progression = [int(val) for val in data[1]]
    i = partition(progression, 0, n - 1)
    result = [str(val) for val in progression]
    result[i] = "[" + result[i] + "]"
    print(" ".join(result))

Solution (Python):
length = int(input())
target = [int(n) for n in input().split(" ")]
splitter = target[-1]
border = 0
for i, n in enumerate(target):
    if n <= splitter:
        target[i], target[border] = target[border], target[i]
        border += 1
target[border - 1] = [splitter]
print(*target)

Solution (Python):
length = int(input())
target = [int(n) for n in input().split(" ")]
splitter = target[-1]
border = 0
for i, n in enumerate(target):
    if n <= splitter:
        target[i], target[border] = target[border], target[i]
        border += 1
target[border - 1] = [splitter]
print(*target)

Solution (Python):
length = int(input())
target = [int(n) for n in input().split(" ")]
splitter = target[-1]
border = 0
for i, n in enumerate(target):
    if n <= splitter:
        target[i], target[border] = target[border], target[i]
        border += 1
target[border - 1] = [splitter]
print(*target)

Solution (Python):
length = int(input())
target = [int(n) for n in input().split(" ")]
splitter = target[-1]
border = 0
for i, n in enumerate(target):
    if n <= splitter:
        target[i], target[border] = target[border], target[i]
        border += 1
target[border - 1] = [splitter]
print(*target)

Solution (Python):

def partition(A,p,r):
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j] <= x:
            i = i+1
            (A[i],A[j]) = (A[j],A[i])
    (A[i+1],A[r]) = (A[r],A[i+1])
    return i+1



if __name__ == '__main__':
    n = (int)(input())
    A = list(map(int,input().split()))

    i = partition(A,0,n-1)
    A[i] = "["+str(A[i])+"]"
    print(*A)

Solution (Python):
def partition(A, p, r):
	x = A[r]
	i = p - 1
	for j in xrange(p, r):
		if A[j] <= x:
			i += 1
			[A[i], A[j]] = [A[j], A[i]]
	[A[i+1], A[r]] = [A[r], A[i+1]]
	return A, i+1

n = int(raw_input())
A = map(int, raw_input().split())

newA, q = partition(A, 0, len(A)-1)

for i in range(n-1):
	if i == q:
		print("[{:}]".format(newA[i])),
	else:
		print(newA[i]),
print newA[-1]

Solution (Python):
def partition(A, p, r):
    i = p - 1
    for j in range(p, r + 1):
        if A[j] <= A[r]:
            i += 1
            A[i], A[j] = A[j], A[i]

    return i


n = int(raw_input())
A = map(int, raw_input().split())

q = partition(A, 0, n-1);

A = map(str, A)
A[q] = "[" + A[q] + "]"

print " ".join(A)

Solution (Python):
def partition(A,p,r):
    x = A[r]
    i = p-1
    for j  in range(p,r):
        if A[j] <= x :
            i = i+1
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
    _tmp = A[i+1]
    A[i+1] = A[r]
    A[r] = _tmp 

    return i+1


def main():
    n = int(input())
    Array = list(map(int,input().split()))
    q = partition(Array,0,n-1)
    Array[q] = "[%d]"%Array[q]
    print(" ".join(map(str,Array))) 
  

if __name__ == '__main__':
    main()

Solution (Python):
def partiton(A, p, r):
    x = A[-1]
    i = p - 1

    for j in range(p, r):
        if A[j] <= x:
            i = i + 1
            A[i], A[j] = A[j], A[i]

    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1


_ = int(input())
li = [int(x) for x in input().split(' ')]
q = partiton(li, 0, len(li) - 1)


li[q] = "[%s]" % (li[q])
print(" ".join([str(i) for i in li]))

Solution (Python):
def partition(A,p,r):
    x=A[r]
    i=p-1
    for j in range(p,r):
        if A[j]<=x:
            i+=1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[r]=A[r],A[i+1]
    return i+1

n=int(input())
A=list(map(int,input().split()))
k=partition(A,0,len(A)-1)
front=" ".join(map(str,A[:k]))
back=" ".join(map(str,A[k+1:]))
ans=front+" ["+str(A[k])+"] "+back
print(ans)

Solution (Python):


def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

if __name__ == '__main__':

    n = int(input())
    A = [int(a) for a in input().split()]

    q = partition(A, 0, n-1)

    A[q] = "[" + str(A[q]) + "]"
    print(" ".join(map(str, A)))

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
n = int(input())
A = list(map(int, input().split()))
p = partition(A, 0, n - 1)
A[p] = f"[{A[p]}]"
print(*A)

Solution (Python):
def partition(hoge):
    x = hoge[-1]
    i = -1
    for j in range(len(hoge)):
        if hoge[j] <= x:
            i += 1
            tmp = hoge[i]
            hoge[i] = hoge[j]
            hoge[j] = tmp
    """        
    tmp = hoge[i+1]
    hoge[i+1] = hoge[-1]
    hoge[-1] = tmp
    """
    return i
    
if __name__ == '__main__':
    _ = input()
    hoge = [int(x) for x in input().split()]
    part = partition(hoge)
    ans = list()
    for num, elem in enumerate(hoge):
        if num == part:
            ans.append('[{}]'.format(elem))
        else:
            ans.append(str(elem))
    print (' '.join(ans))

Solution (Python):
def p(A,p,r):
 x=A[r]
 i=p-1
 for j in range(p,r):
  if A[j]<=x:
   i+=1
   A[i],A[j]=A[j],A[i]
 A[i+1],A[r]=A[r],A[i+1]
 return i+1
n=int(input())
A=list(map(int,input().split()))
k=p(A,0,n-1)
A[k]='['+str(A[k])+']'
print(*A)

Solution (Python):
def p(A,p,r):
 x=A[r]
 i=p-1
 for j in range(p,r):
  if A[j]<=x:
   i+=1
   A[i],A[j]=A[j],A[i]
 A[i+1],A[r]=A[r],A[i+1]
 return i+1
n=int(input())
A=list(map(int,input().split()))
k=p(A,0,n-1)
A[k]='['+str(A[k])+']'
print(*A)

Solution (Python):
def p(A,p,r):
 x=A[r]
 i=p-1
 for j in range(p,r):
  if A[j]<=x:
   i+=1
   A[i],A[j]=A[j],A[i]
 A[i+1],A[r]=A[r],A[i+1]
 return i+1
n=int(input())
A=list(map(int,input().split()))
k=p(A,0,n-1)
A[k]='['+str(A[k])+']'
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0;x=A[-1]
for j in range(n):
 if A[j]<=x:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]=A[n],A[i]
print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]=A[n],A[i]
print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]=A[n],A[i]
print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]=A[n],A[i]
print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]=A[n],A[i]
print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]=A[n],A[i]
print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]=A[n],A[i]
print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]=A[n],A[i]
print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))

Solution (Python):
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]=A[n],A[i]
print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))

Solution (Python):
def s():
 n=int(input())-1
 A=list(map(int,input().split()))
 i=0
 for j in range(n):
  if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
 A[i],A[n]=A[n],A[i]
 print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))
if'__main__'==__name__:s()

Solution (Python):
def s():
 n=int(input())-1
 A=list(map(int,input().split()))
 i=0
 for j in range(n):
  if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
 A[i],A[n]=A[n],A[i]
 print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))
if'__main__'==__name__:s()

Solution (Python):
def s():
 n=int(input())-1
 A=list(map(int,input().split()))
 i=0
 for j in range(n):
  if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
 A[i],A[n]=A[n],A[i]
 print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))
if'__main__'==__name__:s()

Solution (Python):
def s():
 n=int(input())-1
 A=list(map(int,input().split()))
 i=0
 for j in range(n):
  if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
 A[i],A[n]=A[n],A[i]
 print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))
if'__main__'==__name__:s()

Solution (Python):
def s():
 n=int(input())-1
 A=list(map(int,input().split()))
 i=0
 for j in range(n):
  if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
 A[i],A[n]=A[n],A[i]
 print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))
if'__main__'==__name__:s()

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            memo = A[i]
            A[i] = A[j]
            A[j] = memo
    memo = A[i+1]
    A[i+1] = x
    A[r] = memo
    return i+1, A

n = int(input())
a = list(map(int, input().split()))

index, aList = partition(a, 0, len(a)-1)
aList[index] = "[" + str(aList[index]) + "]"

print(*aList)

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            memo = A[i]
            A[i] = A[j]
            A[j] = memo
    memo = A[i+1]
    A[i+1] = x
    A[r] = memo
    return i+1, A

n = int(input())
a = list(map(int, input().split()))

index, aList = partition(a, 0, len(a)-1)
aList[index] = "[" + str(aList[index]) + "]"

print(*aList)

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            memo = A[i]
            A[i] = A[j]
            A[j] = memo
    memo = A[i+1]
    A[i+1] = x
    A[r] = memo
    return i+1, A

n = int(input())
a = list(map(int, input().split()))

index, aList = partition(a, 0, len(a)-1)
aList[index] = "[" + str(aList[index]) + "]"

print(*aList)

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p-1
    for k in range(p, r):
        if A[k] <= x:
            i += 1
            A[i], A[k] = A[k], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

n = int(input())
a = list(map(int, input().split()))
std = partition(a, 0, n-1)
for idx, i in enumerate(a):
    if idx == std:
        print("[{0:}]".format(i), end = "")
    else:
        print(i, end = "")
    if idx != n-1:
        print(" ", end = "")
print("")

Solution (Python):
def partition(li, p, r):
    """Separate li with a value of li[r].
    Returns index of the partition value.

    >>> ax = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    >>> partition(ax, 0, 11)
    7
    >>> ax
    [9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12]
    """
    x = li[r]
    i = p - 1
    for j in range(p, r):
        if li[j] <= x:
            i += 1
            li[i], li[j] = li[j], li[i]

    i += 1
    li[i], li[r] = li[r], li[i]

    return i


def run():
    c = int(input())
    ax = [int(n) for n in input().split()]

    p = partition(ax, 0, c-1)
    for (i, a) in enumerate(ax):
        if i == p:
            val = '[{}]'.format(a)
        else:
            val = str(a)

        if i < c-1:
            print(val, end=" ")
        else:
            print(val)


if __name__ == '__main__':
    run()

Solution (Python):
def partition(A):
    p = 1
    r = len(A) - 1
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            key = A[i]
            A[i] = A[j]
            A[j] = key
    key = A[i + 1]
    A[i + 1] = A[r]
    A[r] = key
    print(' '.join(list(map(str, A[1:i + 1]))) + ' [' + str(A[i + 1]) + '] ' + ' '.join(list(map(str, A[i + 2:]))))
    return A, A[i + 1]

N = int(input())
X = list(map(int, input().split()))
N = [0]
N.extend(X)
partition(N)

Solution (Python):
def partition(a, p, r):
    x = a[r]
    i = p - 1
    for j in range(p, r):
        if a[j] <= x:
            i = i + 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[r] = a[r], a[i + 1]
    return(i + 1)

n = int(input())
a = list(map(int, input().split()))

i = partition(a, 0, n - 1)
a[i] = "[" + str(a[i]) + "]"
print(" ".join(map(str, a)))