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

using namespace std;

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;
    }

    if (value(1, 1) < value(1, 2)) return { 1, 1 };
    if (value(1, M - 1) > value(1, M)) return { 1 , M };

    int l = 1, r = M;
    int ans = -1;

    while (l < r) {
        int mid = (l + r) / 2;

        cerr << l << ' ' << r << ' ' << mid << ' ' << ans << '\n';

        int mid_val = value(1, mid);
        int mid1_val = value(1, mid + 1);

        if (mid_val < mid1_val) {
            r = mid - 1;

            if (mid == 1 || value(1, mid - 1) > mid_val){
                ans = mid;
                break;
            }
        } else {
            l = mid + 2;

            if (mid1_val < value(1, mid + 2)) {
                ans = mid + 1;
                break;
            }
        }
    }

    return { 1, ans };
}
