Kst_v2

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

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

bool sh = 0;

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) {
  if (low == high) {
    return ar[low];
  }
  int piv = ar[low];
  Partition(low, high, piv);
  if (sh) {
    cout << "low high" << low << ' ' << high << "\n";
    cout << "piv = " << piv << "\n";
    cout << "Partition\n";
    for (int el: ar) {
      cout << el << ' ';
    }
    cout << "\n\n";
  }
  int lft = low;
  while (ar[lft] != piv) {
    lft++;
  }
  int rgt = high;
  while (ar[rgt] != piv) {
    rgt--;
  }
  // lft - самый левый piv
  // rgt - самый правый piv
  if (sh) {
    cout << "knum = " << knum << "\n";
    cout << "lft rgt " << lft << ' ' << rgt << "\n";
  }
  if (knum < lft - low) {
    if (sh) {
      cout << "A\n";
    }
    return Kst(low, lft - 1, knum);
  }
  if (lft - low <= knum && knum  <= rgt - low) {
    if (sh) {
      cout << "B\n";
    }
    return piv;
  }
  if (knum > rgt - low) {
    if (sh) {
      cout << "C\n";
    }
    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);
}
/*
16
7 10 3 4 5 11 2 1 2 3 1 5 4 6 7 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 1 2 2 3 3 4 4 5 5 6 7 7 10 11

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
*/