//Translator is written by Mys_C_K.
#include<bits/stdc++.h>
using namespace std;
#define YXQ_AK_NOIP_2092 typedef
YXQ_AK_NOIP_2092 long double YXQ_AK_NOIP_2091;
YXQ_AK_NOIP_2092 long long YXQ_AK_NOIP_2090;
#define YXQ_AK_NOIP_2089 else
#define YXQ_AK_NOIP_2088 struct
#define YXQ_AK_NOIP_2087 const
#define YXQ_AK_NOIP_2086 priority_queue
#define YXQ_AK_NOIP_2085 unordered_map
#define YXQ_AK_NOIP_2084 min
#define YXQ_AK_NOIP_2083 inline
#define YXQ_AK_NOIP_2082 return
#define YXQ_AK_NOIP_2081 unsigned
#define YXQ_AK_NOIP_2080 push_back
#define YXQ_AK_NOIP_2079 pair
#define YXQ_AK_NOIP_2078 while
#define YXQ_AK_NOIP_2077 if
#define YXQ_AK_NOIP_2076 upper_bound
#define YXQ_AK_NOIP_2075 delete
#define YXQ_AK_NOIP_2074 memcpy
#define YXQ_AK_NOIP_2073 sizeof
#define YXQ_AK_NOIP_2072 make_pair
#define YXQ_AK_NOIP_2071 queue
#define YXQ_AK_NOIP_2070 namespace
#define YXQ_AK_NOIP_2069 size
#define YXQ_AK_NOIP_2068 second
#define YXQ_AK_NOIP_2067 first
#define YXQ_AK_NOIP_2066 memset
#define YXQ_AK_NOIP_2065 lower_bound
#define YXQ_AK_NOIP_2064 printf
#define YXQ_AK_NOIP_2063 iterator
#define YXQ_AK_NOIP_2062 erase
#define YXQ_AK_NOIP_2061 vector
#define YXQ_AK_NOIP_2060 max
#define YXQ_AK_NOIP_2059 scanf
#define YXQ_AK_NOIP_2058 using
#define YXQ_AK_NOIP_2057 for
#define YXQ_AK_NOIP_2056 sort
#define YXQ_AK_NOIP_2055 false
#define YXQ_AK_NOIP_2054 end
#define YXQ_AK_NOIP_2053 pop
#define YXQ_AK_NOIP_2052 cin
#define YXQ_AK_NOIP_2051 true
#define YXQ_AK_NOIP_2050 find
#define YXQ_AK_NOIP_2049 count
#define YXQ_AK_NOIP_2048 reverse
#define YXQ_AK_NOIP_2047 static
#define YXQ_AK_NOIP_2046 push
#define YXQ_AK_NOIP_2045 endl
#define YXQ_AK_NOIP_2044 unique
#define YXQ_AK_NOIP_2043 empty
#define YXQ_AK_NOIP_2042 begin
#define YXQ_AK_NOIP_2041 insert
#define YXQ_AK_NOIP_2040 cout
#define YXQ_AK_NOIP_2039 std
#define YXQ_AK_NOIP_2038 int
#define YXQ_AK_NOIP_2037 char
#define YXQ_AK_NOIP_2036 swap
#define YXQ_AK_NOIP_2035 new
#define YXQ_AK_NOIP_2034 set
#define YXQ_AK_NOIP_2033 double
#define YXQ_AK_NOIP_2032 map
#define YXQ_AK_NOIP_2031 void
#define YXQ_AK_NOIP_2030 stack
#define YXQ_AK_NOIP_2021 getchar()
#define YXQ_AK_NOIP_2022(YXQ_AK_NOIP_2093,YXQ_AK_NOIP_2103,YXQ_AK_NOIP_2104) YXQ_AK_NOIP_2057(YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2093=YXQ_AK_NOIP_2103;YXQ_AK_NOIP_2093<=YXQ_AK_NOIP_2104;YXQ_AK_NOIP_2093++)
#define YXQ_AK_NOIP_2023(YXQ_AK_NOIP_2093,v) YXQ_AK_NOIP_2022(YXQ_AK_NOIP_2093,0,(YXQ_AK_NOIP_2038)v.YXQ_AK_NOIP_2069()-1)
#define YXQ_AK_NOIP_2024(YXQ_AK_NOIP_2103,YXQ_AK_NOIP_2106) YXQ_AK_NOIP_2066(YXQ_AK_NOIP_2103,0,YXQ_AK_NOIP_2073(YXQ_AK_NOIP_2038)*(YXQ_AK_NOIP_2106+1))
#define YXQ_AK_NOIP_2025 YXQ_AK_NOIP_2033
#define YXQ_AK_NOIP_2026 YXQ_AK_NOIP_2080
#define YXQ_AK_NOIP_2027 YXQ_AK_NOIP_2072
#define YXQ_AK_NOIP_2028 YXQ_AK_NOIP_2067
#define YXQ_AK_NOIP_2029 YXQ_AK_NOIP_2068
YXQ_AK_NOIP_2058 YXQ_AK_NOIP_2070 YXQ_AK_NOIP_2039;
YXQ_AK_NOIP_2092 YXQ_AK_NOIP_2079<YXQ_AK_NOIP_2038,YXQ_AK_NOIP_2038> YXQ_AK_NOIP_2019;
YXQ_AK_NOIP_2092 YXQ_AK_NOIP_2034<YXQ_AK_NOIP_2038>::YXQ_AK_NOIP_2063 YXQ_AK_NOIP_2020;
YXQ_AK_NOIP_2083 YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2094()
{
    YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2095,YXQ_AK_NOIP_2096;YXQ_AK_NOIP_2078((YXQ_AK_NOIP_2096=YXQ_AK_NOIP_2021)<'0'||YXQ_AK_NOIP_2096>'9');
    YXQ_AK_NOIP_2095=YXQ_AK_NOIP_2096^'0';YXQ_AK_NOIP_2078((YXQ_AK_NOIP_2096=YXQ_AK_NOIP_2021)>='0'&&YXQ_AK_NOIP_2096<='9')
	    YXQ_AK_NOIP_2095=(YXQ_AK_NOIP_2095<<1)+(YXQ_AK_NOIP_2095<<3)+(YXQ_AK_NOIP_2096^'0');YXQ_AK_NOIP_2082 YXQ_AK_NOIP_2095;
}
YXQ_AK_NOIP_2087 YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2097=310;YXQ_AK_NOIP_2071<YXQ_AK_NOIP_2038> YXQ_AK_NOIP_2098;
YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2099[YXQ_AK_NOIP_2097],YXQ_AK_NOIP_2100[YXQ_AK_NOIP_2097],YXQ_AK_NOIP_2101[YXQ_AK_NOIP_2097][YXQ_AK_NOIP_2097],YXQ_AK_NOIP_2102[YXQ_AK_NOIP_2097],YXQ_AK_NOIP_2103[YXQ_AK_NOIP_2097][YXQ_AK_NOIP_2097],YXQ_AK_NOIP_2104[YXQ_AK_NOIP_2097][YXQ_AK_NOIP_2097];
YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2105(YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2095,YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2106,YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2107)
{
    YXQ_AK_NOIP_2024(YXQ_AK_NOIP_2099,YXQ_AK_NOIP_2107),YXQ_AK_NOIP_2024(YXQ_AK_NOIP_2100,YXQ_AK_NOIP_2107);
    YXQ_AK_NOIP_2022(YXQ_AK_NOIP_2093,1,YXQ_AK_NOIP_2106) YXQ_AK_NOIP_2024(YXQ_AK_NOIP_2101[YXQ_AK_NOIP_2093],YXQ_AK_NOIP_2107),YXQ_AK_NOIP_2099[YXQ_AK_NOIP_2103[YXQ_AK_NOIP_2093][YXQ_AK_NOIP_2102[YXQ_AK_NOIP_2093]=1]]++;
    YXQ_AK_NOIP_2078(!YXQ_AK_NOIP_2098.YXQ_AK_NOIP_2043()) YXQ_AK_NOIP_2098.YXQ_AK_NOIP_2053();
    YXQ_AK_NOIP_2022(YXQ_AK_NOIP_2093,1,YXQ_AK_NOIP_2107) YXQ_AK_NOIP_2077(YXQ_AK_NOIP_2099[YXQ_AK_NOIP_2093]>YXQ_AK_NOIP_2095) YXQ_AK_NOIP_2098.YXQ_AK_NOIP_2046(YXQ_AK_NOIP_2093),YXQ_AK_NOIP_2100[YXQ_AK_NOIP_2093]=1;
    YXQ_AK_NOIP_2078(!YXQ_AK_NOIP_2098.YXQ_AK_NOIP_2043())
	{
	    YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2108=YXQ_AK_NOIP_2098.front();YXQ_AK_NOIP_2098.YXQ_AK_NOIP_2053();
	    YXQ_AK_NOIP_2022(YXQ_AK_NOIP_2093,1,YXQ_AK_NOIP_2106) YXQ_AK_NOIP_2101[YXQ_AK_NOIP_2093][YXQ_AK_NOIP_2104[YXQ_AK_NOIP_2093][YXQ_AK_NOIP_2108]]=1;
	    YXQ_AK_NOIP_2022(YXQ_AK_NOIP_2093,1,YXQ_AK_NOIP_2106)
		{
		    YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2109=0;
		    YXQ_AK_NOIP_2078(YXQ_AK_NOIP_2102[YXQ_AK_NOIP_2093]<=YXQ_AK_NOIP_2107&&YXQ_AK_NOIP_2101[YXQ_AK_NOIP_2093][YXQ_AK_NOIP_2102[YXQ_AK_NOIP_2093]]) YXQ_AK_NOIP_2102[YXQ_AK_NOIP_2093]++,YXQ_AK_NOIP_2109=1;
		    YXQ_AK_NOIP_2077(YXQ_AK_NOIP_2102[YXQ_AK_NOIP_2093]>YXQ_AK_NOIP_2107) YXQ_AK_NOIP_2082 YXQ_AK_NOIP_2055;
		    YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2110=YXQ_AK_NOIP_2103[YXQ_AK_NOIP_2093][YXQ_AK_NOIP_2102[YXQ_AK_NOIP_2093]];YXQ_AK_NOIP_2077(YXQ_AK_NOIP_2109) YXQ_AK_NOIP_2099[YXQ_AK_NOIP_2110]++;
		    YXQ_AK_NOIP_2077(YXQ_AK_NOIP_2099[YXQ_AK_NOIP_2110]>YXQ_AK_NOIP_2095&&!YXQ_AK_NOIP_2100[YXQ_AK_NOIP_2110]) YXQ_AK_NOIP_2098.YXQ_AK_NOIP_2046(YXQ_AK_NOIP_2110),YXQ_AK_NOIP_2100[YXQ_AK_NOIP_2110]=1;
		}
	}
    YXQ_AK_NOIP_2082 YXQ_AK_NOIP_2051;
}
YXQ_AK_NOIP_2038 main()
{
    YXQ_AK_NOIP_2038 YXQ_AK_NOIP_2106=YXQ_AK_NOIP_2094(),YXQ_AK_NOIP_2107=YXQ_AK_NOIP_2094(),YXQ_AK_NOIP_2111=1,YXQ_AK_NOIP_2112=YXQ_AK_NOIP_2106,YXQ_AK_NOIP_2113=(YXQ_AK_NOIP_2111+YXQ_AK_NOIP_2112)>>1;
    YXQ_AK_NOIP_2022(YXQ_AK_NOIP_2093,1,YXQ_AK_NOIP_2106) YXQ_AK_NOIP_2022(j,1,YXQ_AK_NOIP_2107) YXQ_AK_NOIP_2103[YXQ_AK_NOIP_2093][j]=YXQ_AK_NOIP_2094(),YXQ_AK_NOIP_2104[YXQ_AK_NOIP_2093][YXQ_AK_NOIP_2103[YXQ_AK_NOIP_2093][j]]=j;
    YXQ_AK_NOIP_2078(YXQ_AK_NOIP_2111<=YXQ_AK_NOIP_2112)
	{
	    YXQ_AK_NOIP_2077(YXQ_AK_NOIP_2105(YXQ_AK_NOIP_2113,YXQ_AK_NOIP_2106,YXQ_AK_NOIP_2107)) YXQ_AK_NOIP_2112=YXQ_AK_NOIP_2113-1;
	    YXQ_AK_NOIP_2089 YXQ_AK_NOIP_2111=YXQ_AK_NOIP_2113+1;YXQ_AK_NOIP_2113=(YXQ_AK_NOIP_2111+YXQ_AK_NOIP_2112)>>1;
	}
    YXQ_AK_NOIP_2082 !YXQ_AK_NOIP_2064("%d\n",YXQ_AK_NOIP_2111);
}

Measured memory_bytes: 1408