#include <bits/stdc++.h>
#include "altar.h"

using namespace std;

const int N = 305;

map< pair<int, int>, int> M;

int get(int x, int y) {
    if (M.count({x, y})) return M[{x, y}];
    if (M.count({y, x})) return !M[{y, x}];
    return M[{x, y}] = sense(x, y);
}

int solve(vector<int> p) {
    if (p.size() == 1) return p[0];
    int now = p[0];
    for (int i = 1; i < (int)p.size(); ++i) {
        if (get(p[i], now)) now = p[i];
    }
    vector<int> z;
    for (auto x : p) {
        if (x != now && get(x, now)) z.push_back(x);
    }
    if (z.empty()) return now;
    if (z.size() > 100) z.resize(100);
    return solve(z);
}

int altar(int n) {
    M.clear();
    vector<int> p(n);
    iota(p.begin(), p.end(), 1);
    return solve(p);
}