#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int FindBase(int N){
srand(time(NULL));
vector<int> v;
if(N == 1){
return 0;
}
for(int i = 0;i < N;i++) v.push_back(i);
int cnt = 0;
map<int,int> occur;
vector<int> P;
for(int i = N/3;i < N;i++){
for(int j = 0;j < i*sqrt(i);j++) P.push_back(i);
}
while(cnt < 151){
int a = P[rand() % P.size()], b = P[rand() % P.size()];
if(a == b) continue;
cnt++;
int x = CollectRelics(a,b);
occur[x]++;
}
int best = 0;
for(int i = 0;i < N;i++){
if(occur[best] < occur[i]){
best = i;
}
}
int total = 0;
for(int i = 0;i < N;i++){
if(i == best){
total++;
continue;
}
if(CollectRelics(i,best) != -1) total++;
}
//cout << best;
if(total > (N/2)) return best;
//assert(false);
//cout << best;
return -1;
}
