1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 1000005
int a[N];
int partition(int l,int r){
    int x = a[r],i = l-1;
    for(int j = l;j < r;j++){
        if(a[j] <= x){
            i++;
            swap(a[j],a[i]);
        }
    }
    swap(a[i+1],a[r]);
    return i+1;
}
int find(int l,int r,int k){
    if(l < r){
        int q = partition(l,r);
        int tmp = q+1-l;
        if(tmp == k) return a[q];
        if(k < tmp) return find(l,q-1,k);
        return find(q+1,r,k-tmp);
    }
    else if(l == r) return a[l];
    return -1; 
}
int main(){
    int n,k;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX