#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
typedef long long ll;
const int inf = 0x3f3f3f3f;
struct TreeNode{
int val,siz,cnt;
TreeNode *l,*r;
// TreeNode(int val){
// this -> val = val;
// }
TreeNode(int val)
:val(val),siz(1),cnt(1),l(nullptr),r(nullptr){}
};
void travel(TreeNode *root){
if(root == nullptr) return;
travel(root -> l);
// for(int i = 1;i <= root -> cnt;i++)
// cout << root-val << ' ';
travel(root -> r);
}
TreeNode *findMin(TreeNode *root){
if(root == nullptr) return nullptr;
while(root -> l != nullptr) root = root -> l;
return root;
// if(root -> l == nullptr) return root -> val;
// return findMin(root -> l);
}
TreeNode *findMax(TreeNode *root){
if(root == nullptr) return nullptr;
while(root -> r != nullptr) root = root -> r;
return root;
// if(root -> r == nullptr) return root -> val;
// return findMax(root -> r);
}
bool search(TreeNode *root,int tar){
if(root == nullptr) return false;
if(root -> val == tar) return true;
else if(tar < root -> val) return search(root -> l,tar);
else if(tar > root -> val) return search(root -> r,tar);
else return false;
}
TreeNode *insert(TreeNode *root,int a){
if(root == nullptr) return new TreeNode(a);
if(root -> val == a) (root -> cnt)++;
else if(root -> val > a) root -> l = insert(root -> l,a);
else if(root -> val < a) root -> r = insert(root -> r,a);
root -> siz = root -> cnt + (root -> l ? root -> l -> siz : 0) + (root -> r ? root -> r -> siz : 0);
return root;
}
TreeNode *remove(TreeNode *root,int a){
if(root == nullptr) return root;
if(a < root -> val) root -> l = remove(root -> l,a);
if(a > root -> val) root -> r = remove(root -> r,a);
if(a == root -> val){
if(root -> cnt > 1) (root -> cnt)--;
else{
if(root -> l == nullptr){
TreeNode *tmp = root -> r;
delete root;
root = nullptr;
return tmp;
}
}
int getRank(TreeNode *root,int a){
if(root == nullptr) return 0;
if(root -> val == a) return (root -> l ? root -> l -> siz : 0) + 1;
if(root -> val > a) return getRank(root -> l,a);
else return getRank(root -> r,a) + (root -> l ? root -> l -> siz : 0) + root -> cnt;
}
int query(TreeNode *root,int k){
if(root == nullptr) return -1;
if(root -> l){
if(root -> l -> siz >= k) return query(root -> l,k);
if(root -> l -> siz + root -> cnt >= k) return root -> val;
}
else if(k <= root -> cnt) return root -> val;
else return query(root -> r,k - root -> cnt - (root->l ? root->l->siz : 0));
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
}
