#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
int CollectRelics(int,int);
set<pair<int,int> >st,st2;
int FindBase(int N){
int i;
for(i=0;i<N;i++)
{
st.insert(make_pair(1,i));
}
while(st.size()>=2)
{
//printf("%d %d %d %d %d\n",st.begin()->y,next(st.begin())->y,st.begin()->x,next(st.begin())->x,CollectRelics(st.begin()->y,next(st.begin())->y));
if(st.begin()->x==next(st.begin())->x)
{
int temp=CollectRelics(st.begin()->y,next(st.begin())->y);
if(temp!=-1)
{
st.erase(next(st.begin()));
st.insert(make_pair(st.begin()->x*2,temp));
st.erase(st.begin());
}
else
{
st2.insert(*st.begin());
st.erase(st.begin());
st2.insert(*st.begin());
st.erase(st.begin());
}
}
else
{
st2.insert(*st.begin());
st.erase(st.begin());
}
}
if(st.empty()) return -1;
int las=st.begin()->y;
//printf("las %d sz %d\n",las,sz[las]);
int ans=st.begin()->x;
st.erase(st.begin());
for(set<pair<int,int> >::iterator it=st2.begin();it!=st2.end();it++)
{
int temp=CollectRelics(las,it->y);
if(temp!=-1)
{
las=temp;
ans++;
}
}
if(ans>=N%2?N/2+1:N/2)
return las;
return -1;
}
