template<typename T>
struct persistent_segment_tree {
struct seg {
int l, r;
T cnt;
} tr[4 * N + N * 17];
int root[N], idx;
int build(int l, int r)
{
int p = ++idx;
if (l == r) return p;
int mid = (l + r) >> 1;
tr[p].l = build(l, mid);
tr[p].r = build(mid + 1, r);
return p;
}
int find(vector<int> &v, int x)
{
return lower_bound(v.begin(), v.end(), x) - v.begin();
}
int insert(int p, int l, int r, int x)
{
int q = ++idx;
tr[q] = tr[p];
if (l == r)
{
tr[q].cnt++;
return q;
}
int mid = (l + r) >> 1;
if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
else tr[q].r = insert(tr[p].r, mid + 1, r, x);
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
return q;
}
int query(int q, int p, int l, int r, int k)
{
if (l == r) return r;
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = (l + r) >> 1;
if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}
};