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

#define ll long long
const ll INF=1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,m;
map<int,int>mp;

int get(int id){
      if(mp[id]>0) return mp[id];
      return mp[id]=value(1,id);
}

pair<int,int>find_locmin_point(int N,int M)
{
      n=N;
      m=M;
      int l=1,r=m;
      while(l<=r){
            int mid=(l+r)>>1;
            int val=get(mid);
            int v1=INF;
            if(mid-1>=1) v1=get(mid-1);
            int v2=INF;
            if(mid+1<=m) v2=get(mid+1);
            if(v1>val&&v2>val){
                  return {1,mid};
            }
            else if(v1>v2){
                  l=mid+1;
            }
            else r=mid-1;
      }
      return {1,l-1};
}
