type
  arr=record
    ran,point,lnext,rnext,son:longint;
  end;
var
  tree:array[0..1000000] of arr;
  n,m,root:longint;
procedure update(x:longint);
  begin
  tree[x].son:=tree[tree[x].lnext].son+tree[tree[x].rnext].son+1;
  end;
function splitl(x,sub:longint):longint;
  var
    t:longint;
  begin
    if x=0 then exit(x);
    if tree[x].point<=sub then
       begin
       inc(m);
       t:=m;
       tree[t]:=tree[x];
       tree[t].rnext:=splitl(tree[x].rnext,sub);
       update(t);
       exit(t);
       end
       else exit(splitl(tree[x].lnext,sub));
  end;
function splitr(x,sub:longint):longint;
  var
    t:longint;
  begin
    if x=0 then exit(x);
    if tree[x].point>sub then
       begin
       inc(m);
       t:=m;
       tree[t]:=tree[x];
       tree[t].lnext:=splitr(tree[x].lnext,sub);
       update(t);
       exit(t);
       end
       else exit(splitr(tree[x].rnext,sub));
  end;
function merge(l,r:longint):longint;
  var
    t:longint;
  begin
    if l=0 then exit(r);
    if r=0 then exit(l);
    inc(m);
    t:=m;
    if tree[l].ran<tree[r].ran then
       begin
       tree[t]:=tree[r];
       tree[t].lnext:=merge(l,tree[r].lnext);
       end
       else
       begin
       tree[t]:=tree[l];
       tree[t].rnext:=merge(tree[l].rnext,r);
       end;
    update(t);
    exit(t);
  end;
function dfs(x,sub:longint):longint;
  begin
  if tree[tree[x].lnext].son+1=sub then exit(tree[x].point);
  if tree[tree[x].lnext].son>=sub then exit(dfs(tree[x].lnext,sub))
     else exit(dfs(tree[x].rnext,sub-tree[tree[x].lnext].son-1));
  end;
procedure buildpoint(x:longint);
  begin
  inc(m);
  with tree[m] do
    begin
    point:=x;
    ran:=random(100000)+1;
    lnext:=0;
    rnext:=0;
    son:=1;
    end;
  end;
procedure prepare;
  begin
  randomize;
  fillchar(tree,sizeof(tree),0);
  tree[0].son:=0;
  m:=0;
  buildpoint(-1);
  root:=m;
  end;
procedure work;
  var
    i,x,y:longint;
  begin
  for i:=1 to n do
    begin
    read(x);
    buildpoint(x);
    y:=m;
    root:=merge(merge(splitl(root,x),y),splitr(root,x));
    end;
  end;
begin
  readln(n);
  prepare;
  work;
  writeln(dfs(root,(n+1) div 2+1));
end.