Kst_v1

#include <cmath>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::max;
using std::min;
using std::string;
using std::vector;

void Swap(int* p1, int* p2) {
  int tt = *p1;
  *p1 = *p2;
  *p2 = tt;
}

vector<int> ar;

void Partition(int low, int high, int xnum) {
  // делим на < и >=
  int lft = low - 1;
  for (int id = low; id <= high; ++id) {
    if (ar[id] < xnum) {
      int* p1 = &ar[id];
      int* p2 = &ar[lft + 1];
      Swap(p1, p2);
      lft++;
    }
  }
  // делим на = и >
  for (int id = lft + 1; id <= high; ++id) {
    if (ar[id] == xnum) {
      int* p1 = &ar[id];
      int* p2 = &ar[lft + 1];
      Swap(p1, p2);
      lft++;
    }
  }
}

int Kst(int low, int high, int knum) {
  int piv = ar[low];
  Partition(low, high, piv);
  int lft = low;
  while (ar[lft] != piv) {
    lft++;
  }
  int rgt = high;
  while (ar[rgt] != piv) {
    rgt--;
  }
  // lft - самый левый piv
  // rgt - самый правый piv
  if (knum < lft - low) {
    return Kst(low, lft - 1, knum);
  }
  if (lft - low <= knum <= rgt - low) {
    return piv;
  }
  if (knum > rgt - low) {
    return Kst(rgt + 1, high, knum - (rgt - low + 1));
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  int len;
  int knum;
  cin >> len;
  ar.resize(len);
  for (int& el : ar) {
    cin >> el;
  }
  cin >> knum;
  knum--;
  cout << Kst(0, len - 1, knum);
}
/*
17
2 2 0 2 1 2 0 2 1 0 2 1 2 2 0 0 2

16
7 10 3 4 5 11 2 1 2 3 1 5 4 6 7 1
>= 8 - mist
*/