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):

"""
Created on Thu May  3 21:24:25 2018
ALDS1_6_B
@author: maezawa
"""

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
            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
    
mid = partition(a, 0, len(a)-1)
print(a[0], end='')
for i in range(1, mid):
    print(' {}'.format(a[i]), end='')
print(' [{}]'.format(a[mid]), end='')
for i in range(mid+1,len(a)):
    print(' {}'.format(a[i]), 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

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

A = ['[' + str(A[i]) + ']' if i == pi else str(A[i]) for i in range(len(A))]
print(' '.join(A))

Solution (Python):




import sys

def partition(A, p, r):
    x = A[r]
    i = p-1
    for n in range (p,r):
        if A[n] <= x:
            i += 1
            A[i], A[n] = A[n], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    print(' '.join(map(str,A[:i+1])), end= ' ')
    print('[', A[i+1], ']', sep='', end='')
    if i+1 != r:
        print(' ', end='')
    print(' '.join(map(str,A[i+2:])))


n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
partition(A, 0, n-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

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    j=partition(A,0,n-1)
    for i in range(n):
        if i == n-1:
            print(A[i])
        elif i==j:
            print("[{}]".format(A[i]),end=" ")
        else:
            print(A[i],end=" ")

Solution (Python):
def partition(a_list):
    
    i = 0
    for j in range(len(a_list) - 1):
        if a_list[j] > a_list[len(a_list) - 1]:
            continue
        else:
            a_list[i], a_list[j] = a_list[j], a_list[i]
            i += 1
    a_list[len(a_list) - 1] = '[' + str(a_list[len(a_list) - 1]) + ']'
    a_list[i], a_list[len(a_list) - 1] = a_list[len(a_list) - 1], a_list[i]

n = int(input())
A = list(map(int, input().split()))
partition(A)
print(' '.join(map(str, A)))

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

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]
    return i+1
pivot = partition(a, 0, n)
l = [str(a[i]) for i in range(pivot)]
r = [str(a[i]) for i in range(pivot+1, n)]
print(' '.join(l) +' [' + str(a[pivot]) + '] ' + ' '.join(r))

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

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

    return i + 1


n = int(input())
ary = [int(_) for _ in input().split()]
q = partition(ary, 0, n - 1)
print(*ary[:q], '[{}]'.format(ary[q]), *ary[q + 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())
input_list = list(map(int, input().split(' ')))

q = Partition(input_list, 0, n - 1)

print(*input_list[:q], "[{}]".format(input_list[q]), *input_list[q + 1:])

Solution (Python):
def partition(num_list, start, end):
    split = start -1
    x = num_list[end]
    for i in range(start, end):
        if num_list[i] <= x:
            split += 1
            num_list[split], num_list[i] = num_list[i], num_list[split]
    num_list[split+1], num_list[end] = num_list[end], num_list[split+1]
    num_list = [str(i) for i in num_list]
    num_list[split+1] = '[{}]'.format(num_list[split+1])
    print(' '.join(num_list))

n = int(input())
input_line = [int(i) for i in input().split()]
partition(input_line, 0, n-1)

Solution (Python):
def partition(a, left, right):
    pivot = a[right-1]
    i = left - 1
    for j in range(left, right-1):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[right-1] = a[right-1], a[i+1]
    return i + 1

def main():
    n = int(input())
    a = list(map(int, input().split()))
    p = partition(a, 0, len(a))
    a[p] = '[' + str(a[p]) + ']'
    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-1]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    return i
a = partition(A, 0, n)
A[a] = [A[a]]
A = " ".join([str(num) for num in A])
print(A)

Solution (Python):
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(n - 1):
        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 print_list(A, r):
    for i, e in enumerate(A):
        if i == n - 1:
            print(e)
        elif i == r:
            print([e], end=' ')
        else:
            print(e, end=" ")

n = int(input())
A = [int(e) for e in input().split()]
r = partition(A, 0, -1)
print_list(A, 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
            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, x


def print_list_split_whitespace(a, x):
    ind = 0
    for i, y in enumerate(a):
        if x == y:
            ind = i
    for i in range(len(a) - 1):
        if i == ind:
            print("[" + str(a[i]) + "]", end=" ")
        else:
            print(a[i], end=" ")
    if ind == len(a) - 1:
        print("[" + str(a[-1]) + "]")
    else:
        print(a[-1])


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

q, x = partition(a, 0, n - 1)

print_list_split_whitespace(a, x)

Solution (Python):
def partition(a, left, right):
    pivot = a[right-1]
    i = left - 1
    for j in range(left, right-1):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[right-1] = a[right-1], a[i+1]
    return i + 1
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    p = partition(a, 0, len(a))
    a[p] = '[' + str(a[p]) + ']'
    print(' '.join(map(str, a)))
 
if __name__ == '__main__':
    main()

Solution (Python):
def partition(array, p, r):
    x = array[r]
    i = p-1
    for j in range(p, r):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i+1], array[r] = array[r], array[i+1]
    a1 = array[:i+1]
    a2 = "[" + str(array[i+1]) +  "]"
    a3 = array[i+2:]
    array = a1[:]
    array.append(a2)
    array += a3
    print(*array)
    return i+1

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

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

def main() :
    x = numbers[n - 1]
    i = 0
    for j in range(n) :
        if numbers[j] <= x :
            numbers[i], numbers[j] = numbers[j], numbers[i]
            i += 1

    [print(numbers[j] if j != i - 1 else '['+str(numbers[j])+']', end = ' ' if j != n - 1 else '\n') for j in range(n)]

if __name__ == '__main__':
    main()

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

def main() :
    x = numbers[n - 1]
    i = 0
    for j in range(n) :
        if numbers[j] <= x :
            numbers[i], numbers[j] = numbers[j], numbers[i]
            i += 1

    [print(numbers[j] if j != i - 1 else '['+str(numbers[j])+']', end = ' ' if j != n - 1 else '\n') for j in range(n)]

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

b = partition(A, 0, n-1)
A[b] = '[{0}]'.format(A[b])
print(' '.join(map(str, A)))

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

c = partition(x, 0, n-1)

for i, e in enumerate(x):
    if i == c:
        print '[{0}]'.format(e),
    else:
        print e,

Solution (Python):

from __future__ import division, print_function
from sys import stdin


def patition(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(stdin.readline())
data = [int(s) for s in stdin.readline().split()]
pat = patition(data, 0, len(data)-1)
print(*data[:pat], end=' ')
print('[{}]'.format(data[pat]), *data[pat+1:])

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

if __name__ == "__main__":
    import sys
    N = int(sys.stdin.readline().strip())
    A = [int(e) for e in sys.stdin.readline().strip().split()]
    pivIdx = partition(A, 0, N-1)
    strA = map(str, A)
    strA[pivIdx] = "[{0}]".format(strA[pivIdx])
    print " ".join(strA)

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())
lst = list(map(int, input().split()))

s = partition(lst, 0, n-1)
lst[s] = [lst[s]]
print(*lst)

Solution (Python):
import sys
input = sys.stdin.readline

def Partition(A, p, r):
    i = p - 1
    for j in range(p, r):
        if A[j] <= A[r]:
            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(x) for x in input().split()]
m = Partition(A, 0, n-1)
print(*A[:m], end=' ')
print('[{}]'.format(A[m]), end=' ')
print(*A[m+1:])

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

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


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

ans = [str(a) for a in A]
ans[r] = "[{}]".format(ans[r])

print(" ".join(ans))

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


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

p = 1
r = len(A)-1
par = partition(A,p,r)
for i in range(n):
    if i<par or par<i<n-1:
        print(A[i],end=' ')
    elif i==par:
        print('[',end='')
        print(A[i],end='')
        print(']',end=' ')
    else:
        print(A[i])

Solution (Python):
input()
A = [int(x) for x in list(input().split())]

x = A[-1]
i = -1

r = len(A)

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





A[i] = "[" + str(A[i]) + "]"
print(*A)

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

n = int(input())
S = [*map(int, input().split())]

key = partition(S, 1, n-1)
print(*S[:key],'[{}]'.format(S[key]), *S[key+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]
    output = ""
    for idx, num in enumerate(A):
        if idx == i+1:
            output += "[" + str(num) + "]"
        else:
            output += str(num)
        output += " "
    print(output[:-1])

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

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

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

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

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

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

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


main()

Solution (Python):
import sys
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j, n in enumerate(A[:-1]):
        if n <= x:
            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())
nums = list(map(int, input().split(" ")))
p = partition(nums, 0, len(nums)-1)
nums[p] = "[{}]".format(nums[p])
sys.stdout.write(str(nums[0]))
for n in nums[1:]:
    sys.stdout.write(" {}".format(n))
sys.stdout.write("\n")

Solution (Python):
def partition(arr, start, end):
    criteria = arr[end]
    idx1 = start
    for idx2 in range(start, end):
        if arr[idx2] <= criteria:
            arr[idx1],arr[idx2] = arr[idx2],arr[idx1]
            idx1 += 1
    arr[idx1],arr[end] = arr[end],arr[idx1]
    return idx1


num = int(input())
arr = list(map(int, input().split()))
criteria = partition(arr, 0, num-1)
arr[criteria] = "[" + str(arr[criteria]) + "]"
print(" ".join(map(str, arr)))

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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[R] = '[' + str(A[R]) + ']'  
    A[i + 1], A[R] = A[R], A[i + 1]
    return i + 1


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    partition(A, 0, N - 1)
    print(*A)


if __name__ == '__main__':
    main()

Solution (Python):
def partition(A, p, r):
    i = p-1
    x = A[r]
    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 A, i+1

    

if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().rstrip().split()))
    A, index = partition(A, 0, len(A)-1)
    A_str = ''
    for i in range(len(A)):
        if i == index:
            A_str = A_str + ' [' + str(A[i]) + ']'
        else:
            A_str = A_str + ' '+ str(A[i])
    print(A_str.strip().rstrip())

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

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

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

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
x = A[n-1]
i = -1
for j in range(0, 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]
for j in range(n):
    if j == 0:
        print(A[j], end="")
    elif j-1 == i:
        print(" "+"["+str(A[j])+"]",end ="")
    else:
        print(" "+str(A[j]),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


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

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

    print(*A[0: p], end=" ")
    print(f"[{A[p]}]", end=" ")
    print(*A[p + 1:])


if __name__ == "__main__":
    main()

Solution (Python):
_ = input()
A = list(map(int, input().rstrip().split(" ")))

x = A[-1]

i = 0
j = 0
while i < len(A) - 1:
    if A[i] <= x:
        A[j], A[i] = A[i], A[j]
        j += 1
    i += 1
A[-1], A[j] = A[j], A[-1]
A[j] = "[" + str(A[j]) + "]"

A = list(map(str, A))
print(" ".join(A))in(list(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()))
q = partition(A, 0, n - 1)

print(*A[:q], f"[{A[q]}]", *A[q + 1:])

Solution (Python):
import sys


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(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().split()]

    q = partition(A, 0, N - 1)
    new_A = list(str(x) for x in A)
    new_A[q] = "[" + new_A[q] + "]"
    print(" ".join(new_A))


main()

Solution (Python):
import sys
input = sys.stdin.readline

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

  def swap(a, b):
    tmp=A[a]
    A[a]=A[b]
    A[b]=tmp

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

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

Solution (Python):
N = int(input())
*A, = map(int, input().split())

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

j = partition(A, 0, N - 1)
print(*(str(x) if i != j else "[%d]" % x for i, x in enumerate(A)))

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

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]
    i += 1
    A[i], A[r] = A[r], A[i]
    return i

r = partition(a, 0, n-1)

for i in range(n):
    if i == r:
        print('[', a[i], ']', sep='', end='')
    else:
        print(a[i], end='')
    if i < n-1:
        print(' ', end='')
print()

Solution (Python):
import random
from typing import TypeVar, Callable, List, Tuple, Union
T = TypeVar('T')
Num = Union[int, float]




import random
from typing import TypeVar, Callable, List, Tuple, Union
T = TypeVar('T')
Num = Union[int, float]



def nth_element(L: List[Num], begin: int=-1, end: int=-1, key=lambda x: x) -> int:
    """
    pivot = L[pivot_ind] とする。 'pivot 未満の要素 ... pivot ... pivot 以上の要素' となるよう L を破壊的に並び替える。(O(n))
    最後に基準値の pivot がおさまった場所のインデックスを返す。
    begin <= pivot_ind < end の要請はあるが、begin, end の指定により L[begin:end] に対象を絞り L[pivot_ind] 未満 / 以上に並べ替えることもできる。

    Args:
        L (list)
        pivot_ind (int)
        begin, end (int): L の [begin, end) 半開区間を考える。デフォルトでは L[0:n] となる

    Returns:
        int: 最後に基準値の pivot がおさまった場所のインデックス

    Examples:
        >>> seq = [1, 9, 2, 7, 5, 6, 4, 8, 3, 0]
        >>> nth_element(seq, 4)
        5
        >>> seq
        [1, 2, 0, 4, 3, 5, 7, 8, 9, 6]
        >>> nth_element(seq, 3, begin=3, end=9)
        4
        >>> seq
        [1, 2, 0, 3, 4, 5, 7, 8, 9, 6]
    """
    if begin == -1 and end == -1:
        begin, end = 0, len(L)
    pivot_ind = end-1

    
    end -= 1

    pivot = L[pivot_ind]
    L[pivot_ind], L[end] = L[end], L[pivot_ind]
    
    i = begin - 1
    
    
    for j in range(begin, end):
        if key(L[j]) <= key(pivot):
            i += 1
            L[j], L[i] = L[i], L[j]
    L[i+1], L[end] = L[end], L[i+1]
    return i+1


if __name__ == "__main__":
    n = int(input())
    L = list(map(int, input().split()))
    ind = nth_element(L, 0, n)
    if L[:ind]:
        print(*L[:ind], sep=' ', end=' ')
    print('[{}]'.format(L[ind]), end='')
    if L[ind+1:]:
        print(' ', end='')
    print(*L[ind+1:], sep=' ')

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]
    print(' '.join(map(str, A[:i+1])), end='')
    print(' [', A[i+1], '] ', sep='', end='')
    print( ' '.join(map(str, A[i+2:])))
    
partition(a, 0, n-1)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

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)

A[q] = [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 += 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 resolve():
    n = int(input())
    A = [int(i) for i in input().split()]
    ans = partition(A, 0, len(A) - 1)
    print(*A[:ans], "[{}]".format(A[ans]), *A[ans + 1:])


resolve()

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

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

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

ans = []
for i, j in enumerate(A):
  if i == cnt:
    ans.append("["+str(j)+"]")
  else:
    ans.append(str(j))

print (" ".join(ans))

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n = I()
    A = LI()

    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)
    A_str = [str(i) for i in A]
    A_str[q] = '[' + A_str[q] + ']'
    print(*A_str)

if __name__ == '__main__':
    resolve()

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

idx = partition(A, 0, len(A)-1)
A[idx] = [A[idx]]
print(*A)

Solution (Python):




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

    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


if __name__ == "__main__":
    n = int(input())

    A = [int(i) for i in input().split()]
    x = A[n - 1]
    p = partition(A, 0, n - 1)
    A = ['[' + str(v) + ']' if i == p else str(v) for i, v in enumerate(A)]
    print(' '.join(A))

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

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
    tmp2 = A[i+1]
    A[i+1] = A[r]
    A[r] = tmp2
    return i + 1
if __name__ == "__main__":
    n = int(input())
    A = list(map(int,input().split()))
    q = Partition(A,0,n-1)
    for i in range(n):
        if i:
            print(" ",end = "")
        if i == q:
            print("[",end = "")
        print(str(A[i]),end = "")
        if i == q:
            print("]",end = "")
    print()

Solution (Python):
n=int(input())
nums=list(map(int,input().split()))
def partition(nums,p,r):
    i=p-1
    x=nums[r]
    for k in range(p,r):
        if nums[k]<=x:
            i+=1
            nums[i],nums[k]=nums[k],nums[i]

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

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

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

n = input()
a = list(map(int, input().split()))
q = partition(a, 0, len(a) - 1)
a[q] = '[{}]'.format(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
            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(e) for e in input().split()]
b = partition(A,0,n-1)
A[b] = f"[{A[b]}]"
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
      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(a, 0, n - 1)
a[q] = f"[{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
            esc = a[i]
            a[i] = a[j]
            a[j] = esc
    esc = a[i + 1]
    a[i + 1] = a[r]
    a[r] = esc
    return i + 1


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

index = partition(A, 0, n - 1)
left = A[:index]
center = A[index]
right = A[index + 1:]
print(*left, '[' + str(center) + ']', *right)

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 = [int(i) for i in input().split()]
q = partition(a, 0, n - 1)
a[q] = f"[{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 += 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 = A[-1]
q = partition(A,0,n-1)
s = list(map(str,A))
print(" ".join(s[:q])+" [{}] ".format(s[q])+" ".join(s[q+1:]))

Solution (Python):
n = int(input())
A = [int(i) for i in 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 A, i + 1

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

outputs = [ "["+str(A[i]) + "]" if i == x else str(A[i]) for i in range(len(A))]
print(" ".join(outputs))

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

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,a):
    ans=partition(a,0,n-1)
    print(' '.join(map(str,a[:ans])),end='')
    print(' ['+str(a[ans])+'] ',end='')
    if(ans<n-1):
        print(' '.join(map(str,a[ans+1:])))

    return

if __name__=='__main__':
    n,a=readinput()
    main(n,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
			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

if __name__ == '__main__':
	
	

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

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

	for i in range(n):
		if i:
			print(" ", end="")
		if i == q:
			print("[", end="")
		if i == n - 1:
			print(A[i])
		else:
			print(A[i], end="")
		if i == q:
			print("]", end="")

Solution (Python):
def partition(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]

    return i + 1


def main():
    n = int(input())
    A = list(map(int, input().split()))
    q = partition(A, 0, n-1)
    for i in range(len(A)):
        if i == q:
            A[i] = "[" + str(A[i]) + "]"
        else:
            A[i] = str(A[i])

    print(*A)


if __name__ == "__main__":
    main()