#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 len = dr - st + 1;
        int x = st + len / 3, y = st + 2 * len / 3;
        if (v[x] == -1)
            v[x] = value(1, x);
        if (v[y] == -1)
            v[y] = value(1, y);
        /*if (v[x] == v[y])
            x++;
        if (v[x] == -1)
            v[x] = value(1, x);*/
        if (v[x] <= v[y])
            dr = y - 1;
        else
            st = x + 1;
    }
    if (dr - st <= 5)
    {
        //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);
    }
}
