#include "locmin.h"
#include <bits/stdc++.h>

using namespace std;

using integer = int;

#define int long long

const int inf = 2e18;

pair<integer,integer> find_locmin_point(integer N, integer M)
{
    //cout << N << ' ' << M << endl;
    vector<int> v(M + 3);
    v[0] = v[M + 1] = inf;
    for (int i = 1; i <= M; i++)
        v[i] = -1;
    int st = 1, dr = M;
    //cout << st << ' ' << dr << endl;
    while (dr - st > 5)
    {
        int mij = (st + dr) / 2;
        v[mij] = value(1, mij);
        v[mij + 1] = value(1, mij + 1);
        if (v[mij] < v[mij + 1])
            dr = mij;
        else
            st = mij + 1;
    }
    //cout << st << ' ' << dr << endl;
    v[0] = v[M + 1] = inf;
    for (int i = st - 1; i <= dr + 1; i++)
    {
        if (i >= 1 and i <= M and v[i] == -1)
            v[i] = value(1, i);
    }
    for (int i = st; i <= dr; i++)
    {
        if (v[i] < v[i - 1] and v[i] < v[i + 1])
        {
            return {1, i};
        }
    }
    assert(false);
}
