/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <cstdint>
#include <iostream>
#include <string>

constexpr int32_t kMaxArraySize = 100000;

void CallPartition(std::istream &input_stream);

class Partition {
 public:
  Partition() noexcept;
  ~Partition() noexcept;
  void AddData(const int32_t value);
  void ResetData() noexcept;
  int32_t ComputePartition(const int32_t start, const int32_t end);
  int32_t GetValue(const int32_t index);

 private:
  Partition(const Partition &obj) noexcept = delete;
  Partition &operator=(const Partition &obj) noexcept = delete;
  Partition(Partition &&obj) = delete;
  Partition &operator=(Partition &&obj) = delete;

  void Swap(const int32_t index_1, const int32_t index_2);
  bool IndexOutOfRange(const int32_t index) const noexcept;

 private:
  int32_t size_;
  int32_t values_[kMaxArraySize];
};

void CallPartition(std::istream &input_stream) {
  input_stream.tie(0);
  std::ios::sync_with_stdio(false);
  Partition *partition = new Partition();
  try {
    int32_t count;
    input_stream >> count;
    for (int32_t index = 0; index < count; ++index) {
      int32_t cvalue;
      input_stream >> cvalue;
      partition->AddData(cvalue);
    }
    const int32_t index_pivot = partition->ComputePartition(0, count - 1);
    for (int32_t index = 0; index < count; ++index) {
      if (index != 0) {
        std::cout << " ";
      }
      if (index == index_pivot) {
        std::cout << "[" << partition->GetValue(index) << "]";
      } else {
        std::cout << partition->GetValue(index);
      }
    }
    std::cout << std::endl;
  } catch (...) {
    std::cout << "ERROR" << std::endl;
    throw;
  }
  delete partition;
}

// ****************************************************

Partition::Partition() noexcept : size_(0), values_{} {}
Partition::~Partition() noexcept {}

void Partition::AddData(const int32_t value) {
  if (size_ >= kMaxArraySize) {
    std::cout << "ERROR: AddData(): Data size exceeded a limit = " << kMaxArraySize << std::endl;
    throw 1;
  }
  values_[size_] = value;
  size_++;
}

void Partition::ResetData() noexcept {
  size_ = 0;
}

int32_t Partition::GetValue(const int32_t index) {
  if (IndexOutOfRange(index)) {
    std::cout << "ERROR: GetValue(): Out of range: index = " << index << std::endl;
    throw 1;
  }
  return values_[index];
}

int32_t Partition::ComputePartition(const int32_t start, const int32_t end) {
  int32_t index_pivot = -1;
  if (IndexOutOfRange(start)) {
    std::cout << "ERROR: ComputePartition(): Out of range: start = " << start << std::endl;
    throw 1;
  } else if (IndexOutOfRange(end)) {
    std::cout << "ERROR: ComputePartition(): Out of range: end = " << end << std::endl;
    throw 1;
  } else {
    try {
      const int32_t value_pivot = values_[end];
      int32_t index_store = start;
      for (int32_t index_compare = start; index_compare < end; ++index_compare) {
        if (values_[index_compare] <= value_pivot) {
          Swap(index_compare, index_store);
          ++index_store;
        }
      }
      Swap(end, index_store);
      index_pivot = index_store;
    } catch (...) {
      throw;
    }
  }
  return index_pivot;
}

void Partition::Swap(const int32_t index_1, const int32_t index_2) {
  if (IndexOutOfRange(index_1)) {
    std::cout << "ERROR: Swap(): Out of range: index_1 = " << index_1 << std::endl;
    throw 1;
  } else if (IndexOutOfRange(index_2)) {
    std::cout << "ERROR: Swap(): Out of range: index_2 = " << index_2 << std::endl;
    throw 1;
  } else {
    const int32_t temp = values_[index_2];
    values_[index_2] = values_[index_1];
    values_[index_1] = temp;
  }
}

bool Partition::IndexOutOfRange(const int32_t index) const noexcept {
  return ((index) < 0 || (index >= size_));
}

int main(int argc, char *argv[]) {
  try {
    CallPartition(std::cin);
  } catch (...) {
    std::cout << "ERROR: Main" << std::endl;
  }
  return 0;
}




Measured memory_bytes: 3320