#include "locmin.h"
#include <bits/stdc++.h>
using namespace std;

long long A[1001], MM;

int divide_and_conquer(int l, int r){
    if(l > r) return -1;
    if(l == r){
        return l;
    }
    int m = (l + r) / 2;
    long long v_mid = (A[m] != 0 ? A[m] : A[m] = value(1, m));
    long long v_right = (m + 1 <= MM ? A[m + 1] != 0 ? A[m + 1] : A[m + 1] = value(1, m + 1) : 2e18);
    long long v_left = (m - 1 >= 1 ? A[m - 1] != 0 ? A[m - 1] : A[m - 1] = value(1, m - 1) : 2e18);
    if(v_mid < v_right && v_mid < v_left){
        return m;
    }
    int res = -1;
    if(v_mid > v_right) res = divide_and_conquer(m + 1, r);
    if(res == -1 && v_mid > v_left) res = divide_and_conquer(l, m - 1);
    return res;
}

pair<int, int> find_locmin_point(int N, int M) {
    if(M == 1){
        return {1, 1};
    }
    if(M == 2){
        if(value(1, 1) > value(1, 2)){
            return {1, 2};
        }
        return {1, 1};
    }
    MM = M;
    return {1, divide_and_conquer(1, M)};
}
