#include <bits/stdc++.h>
#include <vector>
#include <algorithm>

extern int query(int x, int y);

int solve(int n) {
    std::vector<std::array<int, 3>> diagonals;

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            // kihagyjuk a szomszédos vagy azonos csúcsokat (nem átlók)
            if ((j - i + n) % n == 1 || (i - j + n) % n == 1 || i == j)
                continue;

            // távolság 0 csúcstól
            int left = std::min((i - 0 + n) % n, (j - 0 + n) % n);
            int right = std::min((0 - i + n) % n, (0 - j + n) % n);
            int d = std::max(left, right);

            diagonals.push_back({d, i, j});
        }
    }

    // növekvő távolság szerint rendezés
    std::sort(diagonals.begin(), diagonals.end());

    // lekérdezés legközelebbi átlóktól kezdve
    for (const auto& tup : diagonals) {
        int i = std::get<1>(tup);
        int j = std::get<2>(tup);
        if (query(i, j)) {
            return i * n + j;
        }
    }

    return -1; // elméletileg nem fordulhat elő, mindig van legalább 1 átló
}