#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <vector>
#include "locmin.h"

std::pair<int, int> find_locmin_point(int N, int M) {
    std::vector<long long> values(N * M, 0);
    const auto v = [N, M, &values] (int r, int c) {
        if (r < 0 || c < 0 || r >= N || c >= M) return LLONG_MAX;
        if (values[r * M + c] == 0) values[r * M + c] = value(r + 1, c + 1);
        return values[r * M + c];
    };

    for (int i = 0; i < N; i++) {
        int l = 0, r = M;
        while (l < r) {
            int m = (l + r) / 2;
            if (v(i, m - 1) < v(i, m)) r = m;
            else if (v(i, m) > v(i, m + 1)) l = m + 1;
            else l = r = m;
        }
        if (v(i - 1, l) < v(i, l) || v(i + 1, l) < v(i, l)) continue;
        return { i + 1, l + 1 };
    }
    exit(-1);
}
