代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<stdlib.h>

#define Max(a,b) ((a)>(b)?

(a):(b))

using namespace std;

struct Node

{

    int value;

    Node* l;

    Node* r;

    int BF;		//左子树高度 - 右子树高度

    void init(int v)

    {

        value=v;

        l=NULL;

        r=NULL;

        BF=0;

    }

};

int Abs(int a)

{

    return a>=0?a:-a;

}

int getBF(Node* p)

{

    if(p == NULL)

        return -1;

    return p->BF;

}

bool isBalanced(Node* p)

{

    return Abs(getBF(p->l) - getBF(p->r)) < 2;

}

Node* LL(Node* p)

{

    Node* child = p->l;

    p->l = child->r;

    child->r = p;

    p->BF = Max(getBF(p->l),getBF(p->r)) + 1;

    child->BF = Max(getBF(child->l),getBF(child->r)) + 1;

    return child;

}

Node* RR(Node* p)

{

    Node* child = p->r;

    p->r= child->l;

    child->l = p;

    p->BF = Max(getBF(p->l),getBF(p->r)) + 1;

    child->BF = Max(getBF(child->l),getBF(child->r)) + 1;

    return child;

}

Node* LR(Node* p)

{

    Node* child = p->l;

    p->l = RR(child);

    return LL(p);

}

Node* RL(Node* p)

{

    Node* child = p->r;

    p->r =LL(child);

    return RR(p);

}

Node* Insert(Node* p,int x)

{

    if(p!=NULL)

    {

        if(x>p->value)		//R

        {

            p->r= Insert(p->r,x);

            if(!isBalanced(p))

            {

                if(x> p->r->value)	//R-R

                    p = RR(p);

                else							//R-L

                   p=RL(p);

            }

        }

        else							//L

        {

            p->l= Insert(p->l,x);

            if(!isBalanced(p))

            {

                if(x > p->l->value)	//L-R

                    p = LR(p);

                else							//L-L

                    p = LL(p);

            }

        }

    }

    else

    {

        p=(Node*)malloc(sizeof(Node));

        (*p).init(x);

    }

    p->BF = Max(getBF(p->l),getBF(p->r)) + 1;

    return p;

}

/*void PrintTree(Node* root)//先序遍历AVL树

{

    if(root != NULL)

    {

        cout<<root->value<<"--";

        PrintTree(root->l);

        PrintTree(root->r);

    }

}*/

int main()

{

    int n;

    while(scanf("%d",&n)==1)

    {

        Node* root=NULL;

        int x;

        for(int i=0; i<n; i++)

        {

            scanf("%d",&x);

            root=Insert(root,x);

        }

        printf("%d\n",root->value);

        //PrintTree(root);

    }

    return 0;

}