#include <bits/stdc++.h>
#include <algorithm>
#ifdef ONLINE_JUDGE
#define endl "\n"
#endif
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PII;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(100);
VI answer;
template <typename T>
struct Node {
T val, count;
T lazycount, lazysub;
int pos;
int prior;
Node *l, *r;
inline void set(T _val, int idx) {
pos = idx;
val = _val;
}
Node()
: count(0),
lazycount(0),
lazysub(0),
l(nullptr),
r(nullptr),
prior(rng()) {
}
};
Node<int> nodes[200000 + 1];
int nodecount = 0;
using pnode = Node<int> *;
// tick
inline void pushlazy(pnode t) {
if (not t)
return;
if (t->lazycount) {
t->count += t->lazycount;
t->val += t->lazysub;
if (t->l)
t->l->lazycount += t->lazycount, t->l->lazysub += t->lazysub;
if (t->r)
t->r->lazycount += t->lazycount, t->r->lazysub += t->lazysub;
t->lazycount = 0;
t->lazysub = 0;
}
}
// tick
void split_by_val(pnode t, pnode &l, pnode &r, int val) {
if (not t) {
l = r = nullptr;
return;
}
pushlazy(t);
if (t->val <= val) {
split_by_val(t->r, t->r, r, val);
l = t;
} else {
split_by_val(t->l, l, t->l, val);
r = t;
}
}
// tick
void merge(pnode &t, pnode l, pnode r) {
pushlazy(l);
pushlazy(r);
if (not l or not r)
t = l ? l : r;
else if (l->prior > r->prior) {
merge(l->r, l->r, r);
t = l;
} else {
merge(r->l, l, r->l);
t = r;
}
}
void decrement(pnode t, int val) {
if (t) {
t->lazysub -= val;
t->lazycount += 1;
}
}
// tick
void gen_answer(pnode t) {
if (not t)
return;
pushlazy(t);
gen_answer(t->l);
assert(answer[t->pos] == -1);
answer[t->pos] = t->count;
gen_answer(t->r);
}
// tick
void insert_by_val(pnode &t, pnode it) {
if (not t) {
t = it;
return;
}
if (not it)
return;
pushlazy(t);
if (it->prior > t->prior) {
split_by_val(t, it->l, it->r, it->val);
t = it;
} else if (t->val <= it->val)
insert_by_val(t->r, it);
else
insert_by_val(t->l, it);
}
void insert_all(pnode &target, pnode source) {
if (not source)
return;
pushlazy(source);
insert_all(target, source->l);
insert_all(target, source->r);
source->l = source->r = nullptr;
insert_by_val(target, source);
}
int maxdepth = 0;
void preorder(pnode treap, int depth = 0) {
if (treap) {
maxdepth = max(maxdepth, depth);
// cout << treap->pos << ": ";
// cout << (treap->l ? treap->l->pos : -1) << " ";
// cout << (treap->r ? treap->r->pos : -1) << endl;
preorder(treap->l, depth + 1);
preorder(treap->r, depth + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
Node<int> *treap = nullptr;
int n = 1000;
for (int i = 0; i < n; i++) {
auto nd = new Node<int>();
nd->set(0, i);
insert_by_val(treap, nd);
}
preorder(treap);
cout << maxdepth << endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaWZkZWYgT05MSU5FX0pVREdFCiNkZWZpbmUgZW5kbCAiXG4iCiNlbmRpZgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0eXBlZGVmIGxvbmcgbG9uZyBMTDsKdHlwZWRlZiB2ZWN0b3I8aW50PiBWSTsKdHlwZWRlZiB2ZWN0b3I8Vkk+IFZWSTsKdHlwZWRlZiBwYWlyPGludCwgaW50PiBQSUk7CgptdDE5OTM3IHJuZyhjaHJvbm86OnN0ZWFkeV9jbG9jazo6bm93KCkudGltZV9zaW5jZV9lcG9jaCgpLmNvdW50KCkpOwovLyBtdDE5OTM3IHJuZygxMDApOwpWSSBhbnN3ZXI7Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4Kc3RydWN0IE5vZGUgewogICAgVCB2YWwsIGNvdW50OwogICAgVCBsYXp5Y291bnQsIGxhenlzdWI7CgogICAgaW50IHBvczsKICAgIGludCBwcmlvcjsKICAgIE5vZGUgKmwsICpyOwoKICAgIGlubGluZSB2b2lkIHNldChUIF92YWwsIGludCBpZHgpIHsKICAgICAgICBwb3MgPSBpZHg7CiAgICAgICAgdmFsID0gX3ZhbDsKICAgIH0KICAgIE5vZGUoKQogICAgICAgIDogY291bnQoMCksCiAgICAgICAgICBsYXp5Y291bnQoMCksCiAgICAgICAgICBsYXp5c3ViKDApLAogICAgICAgICAgbChudWxscHRyKSwKICAgICAgICAgIHIobnVsbHB0ciksCiAgICAgICAgICBwcmlvcihybmcoKSkgewogICAgfQp9OwpOb2RlPGludD4gbm9kZXNbMjAwMDAwICsgMV07CmludCBub2RlY291bnQgPSAwOwp1c2luZyBwbm9kZSA9IE5vZGU8aW50PiAqOwoKLy8gdGljawppbmxpbmUgdm9pZCBwdXNobGF6eShwbm9kZSB0KSB7CiAgICBpZiAobm90IHQpCiAgICAgICAgcmV0dXJuOwogICAgaWYgKHQtPmxhenljb3VudCkgewogICAgICAgIHQtPmNvdW50ICs9IHQtPmxhenljb3VudDsKICAgICAgICB0LT52YWwgKz0gdC0+bGF6eXN1YjsKCiAgICAgICAgaWYgKHQtPmwpCiAgICAgICAgICAgIHQtPmwtPmxhenljb3VudCArPSB0LT5sYXp5Y291bnQsIHQtPmwtPmxhenlzdWIgKz0gdC0+bGF6eXN1YjsKICAgICAgICBpZiAodC0+cikKICAgICAgICAgICAgdC0+ci0+bGF6eWNvdW50ICs9IHQtPmxhenljb3VudCwgdC0+ci0+bGF6eXN1YiArPSB0LT5sYXp5c3ViOwoKICAgICAgICB0LT5sYXp5Y291bnQgPSAwOwogICAgICAgIHQtPmxhenlzdWIgPSAwOwogICAgfQp9CgovLyB0aWNrCnZvaWQgc3BsaXRfYnlfdmFsKHBub2RlIHQsIHBub2RlICZsLCBwbm9kZSAmciwgaW50IHZhbCkgewogICAgaWYgKG5vdCB0KSB7CiAgICAgICAgbCA9IHIgPSBudWxscHRyOwogICAgICAgIHJldHVybjsKICAgIH0KCiAgICBwdXNobGF6eSh0KTsKCiAgICBpZiAodC0+dmFsIDw9IHZhbCkgewogICAgICAgIHNwbGl0X2J5X3ZhbCh0LT5yLCB0LT5yLCByLCB2YWwpOwogICAgICAgIGwgPSB0OwogICAgfSBlbHNlIHsKICAgICAgICBzcGxpdF9ieV92YWwodC0+bCwgbCwgdC0+bCwgdmFsKTsKICAgICAgICByID0gdDsKICAgIH0KfQoKLy8gdGljawp2b2lkIG1lcmdlKHBub2RlICZ0LCBwbm9kZSBsLCBwbm9kZSByKSB7CiAgICBwdXNobGF6eShsKTsKICAgIHB1c2hsYXp5KHIpOwogICAgaWYgKG5vdCBsIG9yIG5vdCByKQogICAgICAgIHQgPSBsID8gbCA6IHI7CiAgICBlbHNlIGlmIChsLT5wcmlvciA+IHItPnByaW9yKSB7CiAgICAgICAgbWVyZ2UobC0+ciwgbC0+ciwgcik7CiAgICAgICAgdCA9IGw7CiAgICB9IGVsc2UgewogICAgICAgIG1lcmdlKHItPmwsIGwsIHItPmwpOwogICAgICAgIHQgPSByOwogICAgfQp9Cgp2b2lkIGRlY3JlbWVudChwbm9kZSB0LCBpbnQgdmFsKSB7CiAgICBpZiAodCkgewogICAgICAgIHQtPmxhenlzdWIgLT0gdmFsOwogICAgICAgIHQtPmxhenljb3VudCArPSAxOwogICAgfQp9CgovLyB0aWNrCnZvaWQgZ2VuX2Fuc3dlcihwbm9kZSB0KSB7CiAgICBpZiAobm90IHQpCiAgICAgICAgcmV0dXJuOwogICAgcHVzaGxhenkodCk7CiAgICBnZW5fYW5zd2VyKHQtPmwpOwogICAgYXNzZXJ0KGFuc3dlclt0LT5wb3NdID09IC0xKTsKICAgIGFuc3dlclt0LT5wb3NdID0gdC0+Y291bnQ7CiAgICBnZW5fYW5zd2VyKHQtPnIpOwp9CgovLyB0aWNrCnZvaWQgaW5zZXJ0X2J5X3ZhbChwbm9kZSAmdCwgcG5vZGUgaXQpIHsKICAgIGlmIChub3QgdCkgewogICAgICAgIHQgPSBpdDsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBpZiAobm90IGl0KQogICAgICAgIHJldHVybjsKICAgIHB1c2hsYXp5KHQpOwogICAgaWYgKGl0LT5wcmlvciA+IHQtPnByaW9yKSB7CiAgICAgICAgc3BsaXRfYnlfdmFsKHQsIGl0LT5sLCBpdC0+ciwgaXQtPnZhbCk7CiAgICAgICAgdCA9IGl0OwogICAgfSBlbHNlIGlmICh0LT52YWwgPD0gaXQtPnZhbCkKICAgICAgICBpbnNlcnRfYnlfdmFsKHQtPnIsIGl0KTsKICAgIGVsc2UKICAgICAgICBpbnNlcnRfYnlfdmFsKHQtPmwsIGl0KTsKfQoKdm9pZCBpbnNlcnRfYWxsKHBub2RlICZ0YXJnZXQsIHBub2RlIHNvdXJjZSkgewogICAgaWYgKG5vdCBzb3VyY2UpCiAgICAgICAgcmV0dXJuOwogICAgcHVzaGxhenkoc291cmNlKTsKICAgIGluc2VydF9hbGwodGFyZ2V0LCBzb3VyY2UtPmwpOwogICAgaW5zZXJ0X2FsbCh0YXJnZXQsIHNvdXJjZS0+cik7CiAgICBzb3VyY2UtPmwgPSBzb3VyY2UtPnIgPSBudWxscHRyOwogICAgaW5zZXJ0X2J5X3ZhbCh0YXJnZXQsIHNvdXJjZSk7Cn0KCmludCBtYXhkZXB0aCA9IDA7CnZvaWQgcHJlb3JkZXIocG5vZGUgdHJlYXAsIGludCBkZXB0aCA9IDApIHsKICAgIGlmICh0cmVhcCkgewogICAgICAgIG1heGRlcHRoID0gbWF4KG1heGRlcHRoLCBkZXB0aCk7CiAgICAgICAgLy8gY291dCA8PCB0cmVhcC0+cG9zIDw8ICI6ICI7CiAgICAgICAgLy8gY291dCA8PCAodHJlYXAtPmwgPyB0cmVhcC0+bC0+cG9zIDogLTEpIDw8ICIgIjsKICAgICAgICAvLyBjb3V0IDw8ICh0cmVhcC0+ciA/IHRyZWFwLT5yLT5wb3MgOiAtMSkgPDwgZW5kbDsKCiAgICAgICAgcHJlb3JkZXIodHJlYXAtPmwsIGRlcHRoICsgMSk7CiAgICAgICAgcHJlb3JkZXIodHJlYXAtPnIsIGRlcHRoICsgMSk7CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShudWxscHRyKTsKCiAgICBOb2RlPGludD4gKnRyZWFwID0gbnVsbHB0cjsKICAgIGludCBuID0gMTAwMDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgYXV0byBuZCA9IG5ldyBOb2RlPGludD4oKTsKICAgICAgICBuZC0+c2V0KDAsIGkpOwogICAgICAgIGluc2VydF9ieV92YWwodHJlYXAsIG5kKTsKICAgIH0KCiAgICBwcmVvcmRlcih0cmVhcCk7CiAgICBjb3V0IDw8IG1heGRlcHRoIDw8IGVuZGw7CgogICAgcmV0dXJuIDA7Cn0K