#pragma once
#ifndef __PROTECTOR_ACMOJ_1040__
#define __PROTECTOR_ACMOJ_1040__
#include <functional>
#include <random>
typedef bool (*Comparator)(const int &, const int &);
std::mt19937 rnd(std::random_device{}());
void nth_element(int *first, int *nth, int *last,
                 Comparator comp) {
  if (nth == last) return;
  while (last - first > 1) {
    int *p = first, *q = last - 1, *i = first, *j = last - 1;
    int pivot = *(first + rnd() % (last - first));
    while (i < j) {
      while (comp(*i, pivot)) ++i;
      while (comp(pivot, *j)) --j;
      if (i <= j) {
        std::swap(*i, *j);
        ++i;
        --j;
      }
    }
    if (nth <= j)
      last = j + 1;
    else
      first = i;
  }
}
void sort(int *first, int *last,
          Comparator comp) {
  if (last - first <= 1) return;
  int *mid = first + (last - first) / 2;
  nth_element(first, mid, last, comp);
  sort(first, mid, comp);
  sort(mid, last, comp);
}
#endif