//1066 Root of AVL Tree [重要 待分析 天勤] 算法下P325 平衡二叉树
#include <iostream>
using namespace std;
typedef struct BTNode{
int data;
struct BTNode *lChild,*rChild;
}BTNode;//C C++ 通用定义方式
BTNode* rotateL(BTNode *root){
BTNode *t = root->rChild;
root->rChild = t->lChild;
t->lChild = root;
return t;
}
BTNode* rotateR(BTNode *root){
BTNode *t = root->lChild;
root->lChild = t->rChild;
t->rChild = root;
return t;
}
BTNode *rotateLR(BTNode *root){
root->lChild = rotateL(root->lChild);
return rotateR(root);
}
BTNode* rotateRL(BTNode *root){
root->rChild = rotateR(root->rChild);
return rotateL(root);
}
int getHeight(BTNode *root){
if(root == NULL) return 0;
return max(getHeight(root->lChild),getHeight(root->rChild))+1;
}
void insert(BTNode *&root,int data){
if(root == NULL){
root = new BTNode();
root->data = data;
root->lChild = root->rChild = NULL;
}else if(data < root->data){
insert(root->lChild,data);
if(getHeight(root->lChild) - getHeight(root->rChild) == 2){
root = data < root->lChild->data ? rotateR(root) : rotateLR(root);
}
}else{ //相等的情况呢？？
insert(root->rChild,data);
if(getHeight(root->lChild) - getHeight(root->rChild) == -2){
root = data > root->rChild->data ? rotateL(root) : rotateRL(root);
}
}
}
int main(){
int N,data;
cin>>N;
BTNode *root = NULL;
for(int i=0;i<N;++i){
cin>>data;
insert(root,data);
}
cout<<root->data;
return 0;
} 
