#include "locmin.h"
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

#define MAXM 500

long long v[MAXM+2];

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,1};
    }
    return {1,2};
  }
  if(M==3){
    if(value(1,1)<value(1,2)){
      return {1,1};
    }
    if(value(1,2)<value(1,3)){
      return {1,2};
    }
    return {1,3};
  }

  v[0]=LLONG_MAX;
  v[M+1]=LLONG_MAX;
  int st=1,dr=M;

  while(st<=2&&dr>=M-2){
    if(v[st]==0){
      v[st]=value(1,st);
    }
    if(st>1&&v[st-1]==0){
      v[st-1]=value(1,st-1);
    }
    if(st<M&&v[st+1]==0){
      v[st+1]=value(1,st+1);
    }

    if(v[st]<v[st-1]&&v[st]<v[st+1]){
      return {1,st};
    }

    if(v[dr]==0){
      v[dr]=value(1,dr);
    }
    if(dr<M&&v[dr+1]==0){
      v[dr+1]=value(1,dr+1);
    }
    if(dr>1&&v[dr-1]==0){
      v[dr-1]=value(1,dr-1);
    }

    if(v[dr]<v[dr-1]&&v[dr]<v[dr+1]){
      return {1,dr};
    }

    st++;
    dr--;
  }
}
