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

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

ll get(int i) {
    if(a[i] == 0) {
        return a[i] = value(1, i);
    } else {
        return a[i];
    }
}

int getset(std::set<int>& s, int x) {
    auto it = s.begin();
    for(int i = 0; i < x; i++) {
        it++;
    }
    return *it;
}

std::pair<int, int> find_locmin_point(int n, int m) {
    srand(time(0));
    const int b = 10;
    std::vector<int> v;
    std::set<int> available;
    for(int i = 1; i <= m; i++) {
        available.insert(i);
    }
    while(true) {
        for(int i = 0; i < b; i++) {
            if(available.empty()) break;
            int pos = rand() % int(available.size());
            int x = getset(available, pos);
            available.erase(x);
            v.push_back(x);
        }
        std::sort(v.begin(), v.end());
        v.erase(std::unique(v.begin(), v.end()), v.end());
        int sz = int(v.size());
        for(int i = 0; i < sz; i++) {
            get(v[i]);
        }
        for(int i = 1; i < sz - 1; i++) {
            if(get(v[i - 1]) > get(v[i]) && get(v[i]) < get(v[i + 1])) {
                return {1, v[i]};
            }
        }
    }
}
