#include "locmin.h"
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
using ll = long long;

const int MAX_M = 500;
ll val[MAX_M + 1];

int left, right, mid;
bool exists_min(int l, int r) {
    std::vector<int> v;
    for(int i = l; i <= r; i++) {
        if(val[i] > -1) {
            v.push_back(i);
        }
    }
    left = right = -1;
    for(int i = 1; i < int(v.size()) - 1; i++) {
        if(val[v[i - 1]] > val[v[i]] && val[v[i]] < val[v[i + 1]]) {
            if(left == -1 || v[i + 1] - v[i - 1] + 1 < right - left + 1) {
                left = v[i - 1];
                mid = v[i];
                right = v[i + 1];
            }
        }
    }
    return left > -1;
}

ll get(int x) {
    if(val[x] > -1) {
        return val[x];
    } else {
        return val[x] = value(1, x);
    }
}

int rand_range(int l, int r) {
    return rand() % (r - l + 1) + l;
}

int find(int l, int r) {
    if(r - l + 1 == 3) {
        return l + 1;
    }
    while(!exists_min(l, r)) {
        int x;
        while(val[x = rand_range(l, r)] > -1);
        val[x] = value(1, x);
    }
    if(get(mid - 1) > get(mid) && get(mid) < get(mid + 1)) {
        return mid;
    } else if(get(left) > get(left + 1) && get(left + 1) < get(left + 2)) {
        return left + 1;
    } else if(get(right - 2) > get(right - 1) && get(right - 1) < get(right)) {
        return right - 1;
    } else {
        return find(left + 1, right - 1);
    }
}

std::pair<int, int> find_locmin_point(int n, int m) {
    srand(time(0));
    for(int i = 1; i <= m; i++) {
        val[i] = -1;
    }
    int x = find(1, m);
    return {1, x};
}