// Forward declaration of queryAPI.
// int query(int x, int y); 
// return int means matrix[x][y].

// n行 * n列
// 二分所有列：最多log(n)上取整次，每次遍历中间一列和L,R (n + 2), 如果最后剩下最后一列，还需要遍历这一列的最小值
// 时间复杂度：最大：log(n)上取整 * (n + 2) + n
// 遍历最中间一列，找出最小值， 然后和L， R比较，继续延伸到左右两边，每次将范围缩小一半
// 列二分 + 行二分：不一定有解
// 行二分：如果是最后一行，时间可能还是n*log(n); 且可能不会有解
class Solution {
public:
    vector<int> getMinimumValue(int n) {
        typedef long long LL; // 可能爆int
        const LL INF = 1e15; // 找一个大数
        // 二分列
        int l = 0, r = n - 1; // 矩阵从0开始
        while (l < r) {
            int mid = (l + r) >> 1; // 求出中间列位置
            int k; // 记录当前值的行位置
            LL val = INF; // 需要更新的最小值，先把val定义成最大
            for (int i = 0; i < n; i ++ ) { // 找中间一列的最小值，遍历中间列（i，mid）
                int t = query(i, mid); // query提供接口，用来确定矩阵中的值
                if (t < val) { // 如果当前值小于val
                    val = t; // 更新val
                    k = i; // 更新k
                }
            }
            LL left = mid ? query(k, mid - 1) : INF; // 如果mid大于0，求出第k行mid-1的值
            LL right = mid + 1 < n ? query(k, mid + 1) : INF; // 如果mid在范围内

            if (val < left && val < right) return {k, mid}; // 找到答案
            if (left < val) r = mid - 1; // 左边有解
            else l = mid + 1; // 右边有解
        }

        // 二分后，最后只剩一列，找出这一列的最小值
        int k;
        LL val = INF;
        for (int i = 0; i < n; i ++ ) {
            int t = query(i, r);
            if (t < val) {
                val = t;
                k = i;
            }
        }

        return {k, r};
    }
};