//Translator is written by Mys_C_K.
#include<bits/stdc++.h>
using namespace std;
#define YXQ_AK_NOIP_67 else
#define YXQ_AK_NOIP_66 struct
#define YXQ_AK_NOIP_65 const
#define YXQ_AK_NOIP_64 priority_queue
#define YXQ_AK_NOIP_63 unordered_map
#define YXQ_AK_NOIP_62 min
#define YXQ_AK_NOIP_61 inline
#define YXQ_AK_NOIP_60 return
#define YXQ_AK_NOIP_59 unsigned
#define YXQ_AK_NOIP_58 while
#define YXQ_AK_NOIP_57 if
#define YXQ_AK_NOIP_56 upper_bound
#define YXQ_AK_NOIP_55 delete
#define YXQ_AK_NOIP_54 memcpy
#define YXQ_AK_NOIP_53 sizeof
#define YXQ_AK_NOIP_52 queue
#define YXQ_AK_NOIP_51 namespace
typedef long long YXQ_AK_NOIP_50;
#define YXQ_AK_NOIP_49 size
#define YXQ_AK_NOIP_48 memset
#define YXQ_AK_NOIP_47 lower_bound
#define YXQ_AK_NOIP_46 printf
#define YXQ_AK_NOIP_45 iterator
typedef long double YXQ_AK_NOIP_44;
#define YXQ_AK_NOIP_43 erase
#define YXQ_AK_NOIP_42 vector
#define YXQ_AK_NOIP_41 max
#define YXQ_AK_NOIP_40 scanf
#define YXQ_AK_NOIP_39 using
#define YXQ_AK_NOIP_38 for
#define YXQ_AK_NOIP_37 sort
#define YXQ_AK_NOIP_36 false
#define YXQ_AK_NOIP_35 end
#define YXQ_AK_NOIP_34 pop
#define YXQ_AK_NOIP_33 cin
#define YXQ_AK_NOIP_32 true
#define YXQ_AK_NOIP_31 find
#define YXQ_AK_NOIP_30 count
#define YXQ_AK_NOIP_29 reverse
#define YXQ_AK_NOIP_28 static
#define YXQ_AK_NOIP_27 push
#define YXQ_AK_NOIP_26 endl
#define YXQ_AK_NOIP_25 unique
#define YXQ_AK_NOIP_24 empty
#define YXQ_AK_NOIP_23 begin
#define YXQ_AK_NOIP_22 insert
#define YXQ_AK_NOIP_21 cout
#define YXQ_AK_NOIP_20 std
#define YXQ_AK_NOIP_19 int
#define YXQ_AK_NOIP_18 char
#define YXQ_AK_NOIP_17 swap
#define YXQ_AK_NOIP_16 new
#define YXQ_AK_NOIP_15 set
#define YXQ_AK_NOIP_14 double
#define YXQ_AK_NOIP_13 map
#define YXQ_AK_NOIP_12 void
#define YXQ_AK_NOIP_11 stack
#define gc getchar()
#define YXQ_AK_NOIP_3(YXQ_AK_NOIP_68,YXQ_AK_NOIP_78,YXQ_AK_NOIP_79) YXQ_AK_NOIP_38(YXQ_AK_NOIP_19 YXQ_AK_NOIP_68=YXQ_AK_NOIP_78;YXQ_AK_NOIP_68<=YXQ_AK_NOIP_79;YXQ_AK_NOIP_68++)
#define YXQ_AK_NOIP_4(YXQ_AK_NOIP_68,v) YXQ_AK_NOIP_3(YXQ_AK_NOIP_68,0,(YXQ_AK_NOIP_19)v.YXQ_AK_NOIP_49()-1)
#define YXQ_AK_NOIP_5(YXQ_AK_NOIP_78,YXQ_AK_NOIP_81) YXQ_AK_NOIP_48(YXQ_AK_NOIP_78,0,YXQ_AK_NOIP_53(YXQ_AK_NOIP_19)*(YXQ_AK_NOIP_81+1))
#define YXQ_AK_NOIP_6 YXQ_AK_NOIP_14
#define YXQ_AK_NOIP_7 push_back
#define YXQ_AK_NOIP_8 make_pair
#define YXQ_AK_NOIP_9 first
#define YXQ_AK_NOIP_10 second
YXQ_AK_NOIP_39 YXQ_AK_NOIP_51 YXQ_AK_NOIP_20;
typedef pair<YXQ_AK_NOIP_19,YXQ_AK_NOIP_19> YXQ_AK_NOIP_1;
typedef YXQ_AK_NOIP_15<YXQ_AK_NOIP_19>::YXQ_AK_NOIP_45 YXQ_AK_NOIP_2;
YXQ_AK_NOIP_61 YXQ_AK_NOIP_19 YXQ_AK_NOIP_69()
{
    YXQ_AK_NOIP_19 YXQ_AK_NOIP_70,YXQ_AK_NOIP_71;YXQ_AK_NOIP_58((YXQ_AK_NOIP_71=gc)<'0'||YXQ_AK_NOIP_71>'9');
    YXQ_AK_NOIP_70=YXQ_AK_NOIP_71^'0';YXQ_AK_NOIP_58((YXQ_AK_NOIP_71=gc)>='0'&&YXQ_AK_NOIP_71<='9')
	    YXQ_AK_NOIP_70=(YXQ_AK_NOIP_70<<1)+(YXQ_AK_NOIP_70<<3)+(YXQ_AK_NOIP_71^'0');YXQ_AK_NOIP_60 YXQ_AK_NOIP_70;
}
YXQ_AK_NOIP_65 YXQ_AK_NOIP_19 YXQ_AK_NOIP_72=310;YXQ_AK_NOIP_52<YXQ_AK_NOIP_19> YXQ_AK_NOIP_73;
YXQ_AK_NOIP_19 YXQ_AK_NOIP_74[YXQ_AK_NOIP_72],YXQ_AK_NOIP_75[YXQ_AK_NOIP_72],YXQ_AK_NOIP_76[YXQ_AK_NOIP_72][YXQ_AK_NOIP_72],YXQ_AK_NOIP_77[YXQ_AK_NOIP_72],YXQ_AK_NOIP_78[YXQ_AK_NOIP_72][YXQ_AK_NOIP_72],YXQ_AK_NOIP_79[YXQ_AK_NOIP_72][YXQ_AK_NOIP_72];
YXQ_AK_NOIP_19 YXQ_AK_NOIP_80(YXQ_AK_NOIP_19 YXQ_AK_NOIP_70,YXQ_AK_NOIP_19 YXQ_AK_NOIP_81,YXQ_AK_NOIP_19 YXQ_AK_NOIP_82)
{
    YXQ_AK_NOIP_5(YXQ_AK_NOIP_74,YXQ_AK_NOIP_82),YXQ_AK_NOIP_5(YXQ_AK_NOIP_75,YXQ_AK_NOIP_82);
    YXQ_AK_NOIP_3(YXQ_AK_NOIP_68,1,YXQ_AK_NOIP_81) YXQ_AK_NOIP_5(YXQ_AK_NOIP_76[YXQ_AK_NOIP_68],YXQ_AK_NOIP_82),YXQ_AK_NOIP_74[YXQ_AK_NOIP_78[YXQ_AK_NOIP_68][YXQ_AK_NOIP_77[YXQ_AK_NOIP_68]=1]]++;
    YXQ_AK_NOIP_58(!YXQ_AK_NOIP_73.YXQ_AK_NOIP_24()) YXQ_AK_NOIP_73.YXQ_AK_NOIP_34();
    YXQ_AK_NOIP_3(YXQ_AK_NOIP_68,1,YXQ_AK_NOIP_82) YXQ_AK_NOIP_57(YXQ_AK_NOIP_74[YXQ_AK_NOIP_68]>YXQ_AK_NOIP_70) YXQ_AK_NOIP_73.YXQ_AK_NOIP_27(YXQ_AK_NOIP_68),YXQ_AK_NOIP_75[YXQ_AK_NOIP_68]=1;
    YXQ_AK_NOIP_58(!YXQ_AK_NOIP_73.YXQ_AK_NOIP_24())
	{
	    YXQ_AK_NOIP_19 YXQ_AK_NOIP_83=YXQ_AK_NOIP_73.front();YXQ_AK_NOIP_73.YXQ_AK_NOIP_34();
	    YXQ_AK_NOIP_3(YXQ_AK_NOIP_68,1,YXQ_AK_NOIP_81) YXQ_AK_NOIP_76[YXQ_AK_NOIP_68][YXQ_AK_NOIP_79[YXQ_AK_NOIP_68][YXQ_AK_NOIP_83]]=1;
	    YXQ_AK_NOIP_3(YXQ_AK_NOIP_68,1,YXQ_AK_NOIP_81)
		{
		    YXQ_AK_NOIP_19 YXQ_AK_NOIP_84=0;
		    YXQ_AK_NOIP_58(YXQ_AK_NOIP_77[YXQ_AK_NOIP_68]<=YXQ_AK_NOIP_82&&YXQ_AK_NOIP_76[YXQ_AK_NOIP_68][YXQ_AK_NOIP_77[YXQ_AK_NOIP_68]]) YXQ_AK_NOIP_77[YXQ_AK_NOIP_68]++,YXQ_AK_NOIP_84=1;
		    YXQ_AK_NOIP_57(YXQ_AK_NOIP_77[YXQ_AK_NOIP_68]>YXQ_AK_NOIP_82) YXQ_AK_NOIP_60 YXQ_AK_NOIP_36;
		    YXQ_AK_NOIP_19 YXQ_AK_NOIP_85=YXQ_AK_NOIP_78[YXQ_AK_NOIP_68][YXQ_AK_NOIP_77[YXQ_AK_NOIP_68]];YXQ_AK_NOIP_57(YXQ_AK_NOIP_84) YXQ_AK_NOIP_74[YXQ_AK_NOIP_85]++;
		    YXQ_AK_NOIP_57(YXQ_AK_NOIP_74[YXQ_AK_NOIP_85]>YXQ_AK_NOIP_70&&!YXQ_AK_NOIP_75[YXQ_AK_NOIP_85]) YXQ_AK_NOIP_73.YXQ_AK_NOIP_27(YXQ_AK_NOIP_85),YXQ_AK_NOIP_75[YXQ_AK_NOIP_85]=1;
		}
	}
    YXQ_AK_NOIP_60 YXQ_AK_NOIP_32;
}
YXQ_AK_NOIP_19 main()
{
    YXQ_AK_NOIP_19 YXQ_AK_NOIP_81=YXQ_AK_NOIP_69(),YXQ_AK_NOIP_82=YXQ_AK_NOIP_69(),YXQ_AK_NOIP_86=1,YXQ_AK_NOIP_87=YXQ_AK_NOIP_81,YXQ_AK_NOIP_88=(YXQ_AK_NOIP_86+YXQ_AK_NOIP_87)>>1;
    YXQ_AK_NOIP_3(YXQ_AK_NOIP_68,1,YXQ_AK_NOIP_81) YXQ_AK_NOIP_3(j,1,YXQ_AK_NOIP_82) YXQ_AK_NOIP_78[YXQ_AK_NOIP_68][j]=YXQ_AK_NOIP_69(),YXQ_AK_NOIP_79[YXQ_AK_NOIP_68][YXQ_AK_NOIP_78[YXQ_AK_NOIP_68][j]]=j;
    YXQ_AK_NOIP_58(YXQ_AK_NOIP_86<=YXQ_AK_NOIP_87)
	{
	    YXQ_AK_NOIP_57(YXQ_AK_NOIP_80(YXQ_AK_NOIP_88,YXQ_AK_NOIP_81,YXQ_AK_NOIP_82)) YXQ_AK_NOIP_87=YXQ_AK_NOIP_88-1;
	    YXQ_AK_NOIP_67 YXQ_AK_NOIP_86=YXQ_AK_NOIP_88+1;YXQ_AK_NOIP_88=(YXQ_AK_NOIP_86+YXQ_AK_NOIP_87)>>1;
	}
    YXQ_AK_NOIP_60 !YXQ_AK_NOIP_46("%d\n",YXQ_AK_NOIP_86);
}

Measured memory_bytes: 1408