1 #include<stdio.h>
  2 #include<math.h>
  3 #define MAXN 1000
  4 struct node{
  5     int left,right,data,height,parent;
  6 };
  7 struct node a[MAXN];
  8 int n;
  9 void read();
 10 void updateHeight(int x);
 11 int getfactor(int x);
 12 int getheight(int x);
 13 void L(int x1,int x2);
 14 void R(int x1,int x2);
 15 int main(){
 16     read();
 17     printf("%d\n",a[a[0].data].data);
 18     return 0;
 19 } 
 20 void read(){
 21     int i,data,pre,now;
 22     scanf("%d",&n);
 23     a[0].data = 0;
 24     for(i=1;i<=n;i++){
 25         a[i].left= -1;
 26         a[i].right=-1;
 27         a[i].height=0;
 28         a[i].parent=-1; 
 29     }
 30     for(i=1;i<=n;i++){
 31         scanf("%d",&data);
 32         if(a[0].data==0) {
 33             a[0].data=i;
 34             a[i].data = data;
 35         }else{
 36             a[i].data = data;
 37             now = a[0].data;
 38             while(now!=-1){
 39                 pre = now;
 40                 if(a[now].data>data){
 41                     now = a[now].left;
 42                 }
 43                 else if(a[now].data<data){
 44                     now = a[now].right;
 45                 }
 46                 else{
 47                     now = -1;
 48                     break;
 49                 }
 50             }
 51             if(a[pre].data < data) a[pre].right = i;
 52             else if(a[pre].data > data) a[pre].left = i;
 53             a[i].parent = pre; 
 54             updateHeight(pre);
 55         }
 56     }
 57     
 58 }
 59 
 60 int getheight(int x){
 61     int lefth,righth;
 62     if(a[x].left==-1) lefth = 0;
 63     else lefth = a[a[x].left].height + 1;
 64     
 65     if(a[x].right==-1) righth = 0;
 66     else righth = a[a[x].right].height + 1;
 67     
 68     if(lefth>righth) return lefth;
 69     else return righth;
 70 }
 71 
 72 void L(int x1,int x2){ //左旋转 
 73     int temp,parent;
 74     temp = a[x2].left;
 75     parent = a[x1].parent;
 76     a[x2].left=-1;
 77     a[x1].right = temp;
 78     if(parent!=-1){
 79         if(a[parent].left==x1) a[parent].left = x2;
 80         else a[parent].right = x2;
 81     }
 82     else{
 83         a[0].data = x2;
 84     }
 85     a[x2].left = x1;
 86     a[x2].parent = parent;
 87     a[x1].parent = x2;
 88     if(temp!=-1) a[temp].parent=x1;
 89     
 90     //更改高度
 91     a[x1].height = getheight(x1);
 92     a[x2].height = getheight(x2);
 93      
 94      
 95     
 96 }
 97 void R(int x1,int x2){ //右旋转 
 98     int temp,parent;
 99     parent = a[x1].parent;
100     temp = a[x2].right;
101     a[x2].right = -1;
102     a[x1].left = temp;
103     a[x2].right = x1;
104     if(parent!=-1){
105         if(a[parent].left==x1) a[parent].left = x2;
106         else a[parent].right=x2;
107         
108     }else{
109         a[0].data = x2;  //更改根结点 
110     }
111     //更改父亲结点指向
112     a[x1].parent = x2;
113     a[x2].parent = parent;
114     if(temp!=-1) a[temp].parent=x1; 
115     
116     a[x1].height = getheight(x1);
117     a[x2].height = getheight(x2);
118     
119 }
120 
121 int getfactor(int x){
122     int left,right;
123     if(a[x].left!=-1) left = a[a[x].left].height +1;
124     else left = 0;
125     if(a[x].right!=-1) right = a[a[x].right].height +1;
126     else right = 0;
127     return (left-right);
128 }
129 void updateHeight(int x){
130     int t=x;
131     int lefth,righth;
132     while(x!=-1){
133         if(a[x].left==-1) lefth = 0;
134         else lefth = a[a[x].left].height + 1;
135         
136         if(a[x].right==-1) righth=0;
137         else righth = a[a[x].right].height + 1;
138         
139         if (lefth>righth)
140         a[x].height =lefth;
141         else a[x].height = righth;
142         x = a[x].parent;
143     }
144     x = t;
145     int now,next,next1,factor,factor1;
146     while(x!=-1){
147         //factor = a[a[x].left].height - a[a[x].right].height;
148         factor = getfactor(x);
149         if(factor==-2){ //右子树重 
150           
151             now = x;
152             next = a[x].right;
153             x = a[x].parent;
154             //factor1 = a[a[next].left].height - a[a[next].right].height;
155             factor1 = getfactor(next);
156             if(factor1==1) {
157                 next1 = a[next].left;
158                 R(next,next1);
159                 next = next1;
160                 L(now,next);
161             }
162             else if(factor1==-1){
163                 L(now,next);
164             }
165         }
166         else if(factor==2){  // 左子树重 
167             now = x;
168             next = a[x].left;
169             x = a[x].parent;
170             //factor1 = a[a[next].left].height - a[a[next].right].height;
171             factor1 = getfactor(next);
172             if(factor1==1) {
173                 R(now,next);
174             }
175             else if(factor1==-1){
176                 next1 = a[next].right;
177                 L(next,next1);
178                 next = next1;
179                 R(now,next);
180             }
181         }
182         else x = a[x].parent;
183     } 
184 }