#include "locmin.h"
#include <utility>

const int MAX_N = 500;
const long long INF = 1e18 + 10;

const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };

long long a[MAX_N + 2][MAX_N + 2];

std::pair <int, int> find_locmin_point(int N, int M) {
    for (int i = 0; i <= N + 1; i++) {
        a[i][0] = a[i][M + 1] = INF;
    }

    for (int i = 0; i <= M + 1; i++) {
        a[0][i] = a[N + 1][i] = INF;
    }

    int l = 1, r = M, ans = -1;
    while (l <= r) {
        int mid1 = (r - l) / 3 + l;
        int mid2 = (r - l) / 3 * 2 + l;

        if (mid1 == mid2) break;

        if (value(1, mid1) < value(1, mid2)) {
            r = mid2 - 1;
            ans = mid1;
        } else {
            l = mid1 + 1;
            ans = mid2;
        }
    }

    return { 1, ans };
}
