#include "lokahia.h"
#include <vector>
#include<stdio.h>
using namespace std;
using pii=pair<int,int>;
vector<vector<pii>> V;
vector<int> W;
int Query(int x,int y){
//printf("%d %d\n",x,y);
if(x==y)return x;
else return CollectRelics(x,y);
}
int FindBase(int N){
for(int i=0;i<N;){
int j=i+1;
int c1=1,c2=0,cur=i;
vector<pii> T;
T.emplace_back(i,1);
while(j<N&&c1!=c2){
int k=Query(cur,j);
if(k==-1){
c2++;
T.emplace_back(j,0);
}
else{
c1++;
cur=k;
T.emplace_back(j,1);
}
j++;
}
W.push_back(cur);
V.push_back(T);
i=j;
}
int sz=V.size();
int cand=W.back();
int num=0;
for(auto &x:V.back())num+=x.second;
for(int i=sz-1;i--;){
int k=Query(cand,W[i]);
if(k==-1){
for(auto &x:V[i])if(x.second==0){
k=Query(cand,x.first);
if(k!=-1){
num++;
cand=k;
}
}
}
else{
for(auto &x:V[i])num+=x.second;
cand=k;
}
}
if(num>N/2)return cand;
else return -1;
}
