#include "locmin.h"

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<map>

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

std::pair <int, int> find_locmin_point(int N, int M) {
    ll start = 1, end = M;
    vll got(M + 2,-1);
    got[0] = 1e18, got[M + 1] = 1e18;
    while (start <= end) {
        ll mid = (start + end) / 2;
        if (got[mid + 1] == -1) {
            got[mid + 1] = value(1, mid + 1);
        }
        if (got[mid] == -1){
            got[mid] = value(1, mid);
        }
        if (got[mid - 1] == -1) {
            got[mid - 1] = value(1, mid - 1);
        }
        if (got[mid - 1] < got[mid]) {
            end = mid - 1;
            continue;
        }
        if (got[mid + 1] < got[mid]) {
            start = mid + 1;
            continue;
        }
        return { 1,mid };
    }
    return { 1, start };
}
