将给定的一系列数字插入初始为空的AVL树，请你输出最后生成的AVL树的根结点的值。
输入格式:
输入的第一行给出一个正整数N（≤20），随后一行给出N个不同的整数，其间以空格分隔。
输出格式:
在一行中输出顺序插入上述整数到一棵初始为空的AVL树后，该树的根结点的值。
输入样例1:
5
88 70 61 96 120
输出样例1:
70
输入样例2:
7
88 70 61 96 120 90 65
输出样例2:
88
代码：
#include <bits/stdc++.h>
using namespace std;
class AVL {
private :
struct node {
int l, r;
int val, dep;
};
int root, num; vector<node> e;
void update(int &p) {
e[p].dep = max(e[e[p].l].dep, e[e[p].r].dep) + 1;
}
void zig(int &p) { //右旋
int q = e[p].l;
e[p].l = e[q].r; e[q].r = p; swap(p, q);
update(q); update(p);
}
void zag(int &p) { //左旋
int q = e[p].r;
e[p].r = e[q].l; e[q].l = p; swap(p, q);
update(q); update(p);
}
void adjust(int &p) {
update(p);
if(e[e[p].l].dep - e[e[p].r].dep >= 2) {
int &q = e[p].l;
if(e[e[q].l].dep < e[e[q].r].dep) {
zag(q);
}
zig(p);
} else if(e[e[p].r].dep - e[e[p].l].dep >= 2) {
int &q = e[p].r;
if(e[e[q].l].dep > e[e[q].r].dep) {
zig(q);
}
zag(p);
}
}
int newpoint(int val) {
node &tmp = e[++num]; tmp.val = val;
tmp.dep = 1;
return num;
}
void insert__(int &p, int val) {
if(p == 0) {
p = newpoint(val); update(p);
return ;
}
if(val < e[p].val) {
insert__(e[p].l, val); adjust(p);
} else {
insert__(e[p].r, val); adjust(p);
}
}
public :
AVL(int siz) {
e.resize(siz + 1); e[0].dep = 0;
root = 0; num = 0;
}
void insert(int val) {
insert__(root, val);
}
int getroot() {
return e[root].val;
}
};
int main() {
// freopen("data.in", "r", stdin);
int n; cin >> n;
AVL T(n);
for(int i = 1; i <= n; i++) {
int x; cin >> x;
T.insert(x);
}
cout << T.getroot();
return 0;
}