#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<map>

#include<stack>

#include<queue>

#include<string>

#include<algorithm>

using namespace std;

const int maxn=;

int n,a[maxn];

struct Node

{

    int num;

    int L,R;

    int LH,RH;

    int fa;

}node[maxn];

int sz;

int root;

void init()

{

    root=;

    sz=;

    node[root].fa=-;

    node[root].L=-,node[root].R=-;

    node[root].num=a[];

    node[root].LH=,node[root].RH=;

}

void dfs(int now)

{

    if(node[now].L!=-) dfs(node[now].L);

    if(node[now].R!=-) dfs(node[now].R);

    node[now].LH=max(node[node[now].L].LH,

                    node[node[now].L].RH)+;

    node[now].RH=max(node[node[now].R].LH,

                    node[node[now].R].RH)+;

}

void Update(int fa,int num,int tag)

{

    sz++;

    node[sz].fa=fa;

    node[sz].L=-,node[sz].R=-;

    node[sz].num=num;

    node[sz].LH=,node[sz].RH=;

    if(tag==) node[fa].R=sz;

    else node[fa].L=sz;

    dfs(root);

}

void Insert(int num)

{

    int p=root;

    while()

    {

        if(num>=node[p].num)

        {

            if(node[p].R!=-) p=node[p].R;

            else { Update(p,num,); break; }

        }

        else

        {

            if(node[p].L!=-) p=node[p].L;

            else { Update(p,num,); break; }

        }

    }

}

void LL(int id)

{

    int Lson=node[id].L;

    Node tmp1=node[id];

    Node tmp2=node[Lson];

    if(tmp1.fa!=-)

    {

        if(node[tmp1.fa].L==id) node[tmp1.fa].L=Lson;

        else node[tmp1.fa].R=Lson;

    }

    node[Lson].fa=tmp1.fa;

    node[Lson].R=id;

    node[id].fa=Lson;

    node[id].L=tmp2.R;

    node[tmp2.R].fa=id;

}

void RR(int id)

{

    int Rson=node[id].R;

    Node tmp1=node[id];

    Node tmp2=node[Rson];

    if(tmp1.fa!=-)

    {

        if(node[tmp1.fa].L==id) node[tmp1.fa].L=Rson;

        else node[tmp1.fa].R=Rson;

    }

    node[Rson].fa=tmp1.fa;

    node[Rson].L=id;

    node[id].fa=Rson;

    node[id].R=tmp2.L;

    node[tmp2.L].fa=id;

}

void LR(int id)

{

    int Lson=node[id].L;

    RR(Lson);

    LL(id);

}

void RL(int id)

{

    int Rson=node[id].R;

    LL(Rson);

    RR(id);

}

void Rotate(int id)

{

    int need=-;

    int p=node[id].fa;

    while()

    {

        if(p==-) break;

        if(abs(node[p].LH-node[p].RH)>) { need=p; break; }

        p=node[p].fa;

    }

    if(need==-) return;

    if(node[need].LH>node[need].RH)

    {

        int Lson=node[need].L;

        if(node[Lson].LH>node[Lson].RH) LL(need);

        else LR(need);

    }

    else

    {

        int Rson=node[need].R;

        if(node[Rson].RH>node[Rson].LH) RR(need);

        else RL(need);

    }

    for(int i=;i<=sz;i++) if(node[i].fa==-) root=i;

    dfs(root);

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    init();

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

    {

        Insert(a[i]);

        Rotate(sz);

    }

    printf("%d\n",node[root].num);

    return ;

}