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

using namespace std;

int solve (int n) {
    auto dist = [&] (int x, int y) {
        if (x == 0 && y == n - 1)
            return n + 1;
        if (abs(x - y) == 1)
            return n + 1;
        if (x == 0) {
            return max(y, n - y);
        }
        if (x > y) {
            swap(x, y);
        }
        return max(x, n - y);
    };
    auto code = [&] (int x, int y) {
        return x * n + y;
    };

    if (query(1, n - 1)) {
        return code(1, n - 1);
    }

    int xAnswer = -1, yAnswer = -1;

    auto verif = [&] (int x, int y) {
        if (xAnswer == -1) {
            xAnswer = x;
            yAnswer = y;
        }
        if (dist(x, y) < dist(xAnswer, yAnswer)) {
            xAnswer = x, yAnswer = y;
        }
    };

    int maxi = 0, mini = n + 1;

    vector<int>v;

    for (int i = 2; i < n - 1; i++) {
        if (query(0, i)) {
            verif(0, i);
            maxi = max(maxi, i);
            mini = min(mini, i);
            v.push_back({i});
        }
    }
    for (int i = 1; i < (int) v.size(); i++) {
        verif(v[i - 1], v[i]);
    }
    verif(1, mini);
    verif(maxi, n - 1);
    return code(xAnswer, yAnswer);
//cout << ans << " - " << n * (n - 3) / 2 << '\n';
}