#include <vector>
#include <iostream>
#include <random>

using namespace std;

// mt19937 gen;

// [l, r]
void QuickSort(vector<int> &a, int l, int r, int k) {
	// if (l == r) return;
	if (r - l + 1 <= 1) // r-l+1 ровно количество элементов
		return;
	// <x, =x, >x
	// (!) <=x, >=x
	int x = a[l + rand() % (r - l + 1)];
	int i = l, j = r; // указатели
	// ..........................
	//      l--i->   <-j--r

	// элементы [l,i)  <=x
	// элементы (j,r]  >=x
	while (i <= j) {
		while (a[i] < x) i++;
		while (a[j] > x) j--;
		// a[i] >= x, a[j] <= x
		if (i <= j) {
			swap(a[i++], a[j--]); // a[i],a[j] = a[j],a[i]
			// j -= 1
			// i += 1
		}
	}
	// ........l.............j..i...................r.
	//               k
	// a[k]

	// элементы [l,i)  <=x
	// элементы (j,r]  >=x
	// j < i
	if (l <= k && k <= j) QuickSort(a, l, j, k); 
	// (j,i) <=x >=x
	if (i <= k && k <= r) QuickSort(a, i, r, k);
}

int main() {
	vector<int> a;
	QuickSort(a, 0, a.size()); // [0,n)
}

// nth_element(a.begin(), a.begin() + k, a.end())