output_description: 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 [  ].
input_description: 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.
attempt: #! python3
  # partition.py - 配列を特定の値で、分割するアルゴリズム
  
  
  def partition(array, p, len_array):
      X = array[len_array]
      i = 0 - 1
      for j in range(p, len_array):
          if array[j] <= X:
              i += 1
              tmp = array[i]
              array[i] = array[j]
              array[j] = tmp
      tmp = array[i + 1]
      array[i + 1] = array[len_array]
      array[len_array] = tmp
  
      return i + 1, array
  
  
  len_array = int(input()) - 1
  array = [int(i) for i in input().split()]
  p = 0  # 配列のスタート位置、今後別の関数で使うことも想定して、変数で渡しておく
  
  index, array = partition(array, p, len_array)
  # print(index)
  # print(array)
  str_array = list(map(str, array))
  # print(str_array)
  str_array[index] = "[{}]".format(str_array[index])
  print(" ".join(str_array))
  
problem_description: 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
      
  
  Note that, in this algorithm, Partition always selects an element A[r] as a
  pivot element around which to partition the array A[p..r].
samples: [{"input": "12\n    13 19 9 5 12 8 7 4 21 2 6 11", "output": "9 5 8 7 4 2 6 [11] 21 13 19 12"}]