{$A+,B-,D+,E-,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 65520,0,655360}
Program Median;
Uses Device;
Const
  MaxN=1501;
Type
  TQueue=Record
    A:Array[1..MaxN+1]Of LongInt;
    Head,Tail:LongInt;
  End;
  PQueue=^TQueue;
Var
  N:LongInt;
  Result:LongInt;
Procedure Load;
Begin
  N:=GetN;
End;
Procedure Run;
Var
  Q1,Q2,Q3,Q4:PQueue;
  CLen,I,J:LongInt;
  Was:Array[1..MaxN]Of Boolean;
  R1,R2:LongInt;
  A1,A2,A3:LongInt;
  Middle:LongInt;
  Frs:Boolean;
Procedure Swap(Var A,B:PQueue);
Var
  T:PQueue;
Begin
  T:=A;
  A:=B;
  B:=T;
End;
Procedure Push(A:PQueue; B:LongInt);
Begin
  A^.A[A^.Head]:=B;
  Inc(A^.Head);
End;
Function Peek(A:PQueue):LongInt;
Begin
  Peek:=A^.A[A^.Tail];
End;
Function Peek2(A:PQueue):LongInt;
Begin
  Peek2:=A^.A[A^.Tail+1];
End;
Function Pop(A:PQueue):LongInt;
Begin
  Pop:=A^.A[A^.Tail];
  Inc(A^.Tail);
End;
Function Empty(A:PQueue):Boolean;
Begin
  Empty:=(A^.Head=A^.Tail);
End;
Procedure Init(A:PQueue);
Begin
  A^.Head:=1;
  A^.Tail:=1;
End;
Function Min(A,B:LongInt):LongInt;
Begin
  If A<B Then Min:=A Else Min:=B;
End;
Function Compare(A,B:LongInt):Boolean;
Var
  Rev,Res:Boolean;
  T,C,Middle:LongInt;
Begin
  If Not Frs Then Begin
    C:=Q3^.A[Q3^.Head-1];
    Middle:=Med3(A,B,C);
    If Middle=A Then Begin
      Compare:=False;
    End Else If Middle=B Then Begin
      Compare:=True;
    End Else Begin
      {gluck}
    End;
    Exit;
  End;
  If A>B Then Begin
    T:=A;
    A:=B;
    B:=T;
    Rev:=True;
  End Else Rev:=False;
  If (A=1) Then Begin
    If (B=N) Then Begin
      Res:=False;
    End Else Begin
      Middle:=Med3(1,B,N);
      If Middle=1 Then Res:=True Else Res:=False;
    End;
  End Else If (B=N) Then Begin
    Middle:=Med3(1,A,N);
    If Middle=N Then Res:=True Else Res:=False;
  End Else Begin
    Middle:=Med3(1,A,B);
    If Middle=1 Then Begin
      Middle:=Med3(1,N,A);
      If Middle=1 Then
        Res:=False
      Else If Middle=N Then
        Res:=True
      Else {Middle=A}
        Res:=True;
    End Else If Middle=A Then Begin
      Middle:=Med3(1,N,A);
      If Middle=1 Then
        Res:=True
      Else If Middle=N Then
        Res:=False
      Else {Middle=A}
        Res:=False;
    End Else {Middle=B} Begin
      Middle:=Med3(1,N,A);
      If Middle=1 Then
        Res:=False
      Else If Middle=N Then
        Res:=True
      Else {Middle=A}
        Res:=True;
    End;
  End;
  If Rev Then Res:=Not Res;
  Compare:=Res;
End;
Label Fin;
Begin
  CLen:=1;
  New(Q1);
  New(Q2);
  New(Q3);
  New(Q4);
  Init(Q1);
  Init(Q2);
  Init(Q3);
  Init(Q4);
  FillChar(Was,SizeOf(Was),False);
  For I:=1 To N Do Begin
    Repeat
      J:=Random(N)+1;
    Until Not Was[J];
    Was[J]:=True;
    Push(Q1,J);
    Swap(Q1,Q2);
  End;
  Swap(Q1,Q2);
  Repeat
    Init(Q3);
    Init(Q4);
    While Not Empty(Q2) Do Begin
      R1:=CLen;
      R2:=Min(CLen,Q2^.Head-Q2^.Tail);
      Frs:=True;
      While (R1>0) And (R2>0) Do Begin
        If (CLen*2>N) And (N-(R1+R2)>=(N+1) Div 2) Then Begin Swap(Q1,Q3); Goto Fin; End;
        If (R1>1) And ((R2<=1) Or (Random(2)=0)) Then Begin
          A1:=Peek(Q1);
          A2:=Peek2(Q1);
          A3:=Peek(Q2);
          Middle:=Med3(A1,A2,A3);
          If Middle=A1 Then Begin
            Push(Q3,Pop(Q2));
            Dec(R2);
            Frs:=False;
          End Else If Middle=A2 Then Begin
            Push(Q3,Pop(Q1));
            Dec(R1);
            Push(Q3,Pop(Q1));
            Dec(R1);
            Frs:=False;
          End Else If Middle=A3 Then Begin
            Push(Q3,Pop(Q1));
            Dec(R1);
            Push(Q3,Pop(Q2));
            Dec(R2);
            Frs:=False;
          End;
        End Else If R2>1 Then Begin
          A1:=Peek(Q2);
          A2:=Peek2(Q2);
          A3:=Peek(Q1);
          Middle:=Med3(A1,A2,A3);
          If Middle=A1 Then Begin
            Push(Q3,Pop(Q1));
            Dec(R1);
            Frs:=False;
          End Else If Middle=A2 Then Begin
            Push(Q3,Pop(Q2));
            Dec(R2);
            Push(Q3,Pop(Q2));
            Dec(R2);
            Frs:=False;
          End Else If Middle=A3 Then Begin
            Push(Q3,Pop(Q2));
            Dec(R2);
            Push(Q3,Pop(Q1));
            Dec(R1);
            Frs:=False;
          End;
        End Else Begin
          If Compare(Peek(Q1),Peek(Q2)) Then Begin
            Push(Q3,Pop(Q2));
            Dec(R2);
            Push(Q3,Pop(Q1));
            Dec(R1);
            Frs:=False;
          End Else Begin
            Push(Q3,Pop(Q1));
            Dec(R1);
            Push(Q3,Pop(Q2));
            Dec(R2);
            Frs:=False;
          End;
        End;
      End;
      While (R1>0) Do Begin
        Push(Q3,Pop(Q1));
        Dec(R1);
      End;
      While (R2>0) Do Begin
        Push(Q3,Pop(Q2));
        Dec(R2);
      End;
      Swap(Q3,Q4);
    End;
    If Not Empty(Q1) Then Begin
      While Not Empty(Q1) Do Push(Q3,Pop(Q1));
    End;
    If Q3^.Head-Q3^.Tail<Q4^.Head-Q4^.Tail Then Swap(Q3,Q4);
    CLen:=CLen*2;
    Swap(Q1,Q3);
    Swap(Q2,Q4);
  Until CLen>=N;
  Fin:
  For I:=1 To N Div 2 Do Pop(Q1);
  Result:=Peek(Q1);
End;
Procedure Save;
Begin
  Answer(Result);
End;
Begin
  RandSeed:=32473124;
  Load;
  Run;
  Save;
End.