#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define Key_value ch[ch[root][1]][0]
using namespace std;
const int maxn = 200000 + 10;
char op[maxn][10];
int opx[maxn];
int s[maxn], e[maxn], cnt;
int a[maxn];
int pre[maxn], ch[maxn][0], size[maxn], key[maxn];
int root, tot1;
//PushUp PushDown
void Update_Add(int r, int v)
{
if(!r) return;
key[r] += v;
add[r] += v;
}
void Update_Rev(int r)
{
if(!r) return;
swap(ch[r][0], ch[r][1]);
rev[r] ^= 1;
}
void PushUp(int r)
{
size[r] = size[ch[r][0]] + size[ch[r][1]] + 1;
}
void PushDown(int r)
{
if(add[r])
{
Update_Add(ch[r][0], add[r]);
Update_Add(ch[r][1], add[r]);
add[r] = 0;
}
if(rev[r])
{
Update_Rev(ch[r][0]);
Update_Rev(ch[r][1]);
rev[r] = 0;
}
}
//初始化部分
void NewNode(int &r, int fa, int v)
{
if(tot2) r = s[tot2--];
else r = ++tot1;
ch[r][0] = ch[r][1] = add[r] = 0;
size[r] = 1;
pre[r] = fa;
key[r] = v;
rev[r] = 0;
add[r] = 0;
}
void Build(int &x, int fa, int l, int r)
{
if(l > r) return;
int mid = (l + r) >> 1;
NewNode(x, fa, a[mid]);
Build(ch[x][0], x, l, mid-1);
Build(ch[x][1], x, mid+1, r);
PushUp(x);
}
void Init()
{
pos = 1;
root = tot1 = tot2 = 0;
add[root] = ch[root][0] = ch[root][1] = pre[root] = key[root] = size[root] = 0;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
NewNode(root, 0, -1);
NewNode(ch[root][1], root, -1);
Build(Key_value, ch[root][1], 1, n);
PushUp(ch[root][1]);
PushUp(root);
}
//
//旋转，0为左旋、1为右旋
void Rotate(int x, int kind)
{
int y = pre[x];
PushDown(y);
PushDown(x);
ch[y][!kind] = ch[x][kind];
pre[ch[x][kind]] = y;
if(pre[y])
ch[pre[y]][ch[pre[y]][1]==y] = x;
pre[x] = pre[y];
ch[x][kind] = y;
pre[y] = x;
PushUp(y);
}
//伸展操作，将r转到goal下面
void Splay(int r, int goal)
{
PushDown(r);
while(pre[r] != goal)
{
if(pre[pre[r]] == goal)
{
Rotate(r, ch[pre[r]][0]==r);
}
else
{
int y = pre[r];
int kind = (ch[pre[y]][0]==y);
if(ch[y][kind] == r)
{
Rotate(r, !kind);
Rotate(r, kind);
}
else
{
Rotate(y, kind);
Rotate(r, kind);
}
}
}
PushUp(r);
if(goal == 0) root = r;
}
//求序列第K个元素的节点
int Kth(int r, int k)
{
PushDown(r);
int t = size[ch[r][0]] + 1;
if(k == t) return r;
else if(k < t) return Kth(ch[r][0], k);
else return Kth(ch[r][1], k-t);
}
//反转区间[l,r]
void Reverse(int l, int r)
{
Splay(Kth(root, l), 0);
Splay(Kth(root, r+2), root);
Update_Rev(Key_value);
PushUp(ch[root][1]);
PushUp(root);
}
//插入操作。在pos位置后插入len个元素 a[0]~a[len-1]
void Insert(int len)
{
int x = Kth(root, pos+1);
int y = Kth(root, pos+2);
Splay(x, 0); Splay(y, root);
Build(Key_value, 0, len-1, ch[root][1]);
PushUp(ch[root][1]);
PushUp(root);
}
//删除节点
void erase(int r)
{
if(r)
{
s[++tot2] = r;
erase(ch[r][0]);
erase(ch[r][1]);
}
}
//删除操作，删除pos位置后面的len个元素 a[pos+1]~a[pos+len]
void Delete(int len)
{
int x = Kth(root, pos+1);
int y = Kth(root, pos+1+len+1);
Splay(x, 0); Splay(y, root);
erase(Key_value);
pre[Key_value] = 0;
Key_value = 0;
PushUp(ch[root][1]);
PushUp(root);
}
//切割插入，将序列第a~b个元素删除并插入到剩余序列的第c个元素后面
void Cut(int a, int b, int c)
{
int x = Kth(root, a);
int y = Kth(root, b+2);
Splay(x, 0);
Splay(y, root);
int tmp = Key_value;
Key_value = 0;
PushUp(ch[root][1]);
PushUp(root);
int z = Kth(root, c+1);
Splay(z, 0);
int m = Get_Min(ch[root][1]);
Splay(m, root);
Key_value = tmp;
pre[Key_value] = ch[root][1];
PushUp(ch[root][1]);
PushUp(root);
}
