#include <bits/stdc++.h>
using namespace std;
int CollectRelics(int,int);
int bu[222],sz[222];
set<int>st,st2;
int FindBase(int N){
int i;
for(i=0;i<N;i++)
{
bu[i]=i;
sz[i]=1;
st.insert(i);
}
while(st.size()>=2)
{
if(sz[*st.begin()]==sz[*next(st.begin())])
{
if(CollectRelics(*st.begin(),*next(st.begin()))!=-1)
{
bu[*next(st.begin())]=*st.begin();
sz[*st.begin()]*=2;
st.erase(next(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());
}
}
int las=*st.begin();
//printf("las %d sz %d\n",las,sz[las]);
int ans=sz[las];
st.erase(st.begin());
for(set<int>::iterator it=st2.begin();it!=st2.end();it++)
{
int temp=CollectRelics(las,*it);
if(temp!=-1)
{
las=temp;
ans++;
}
}
if(ans>=N%2?N/2+1:N/2)
return las;
return -1;
}
