#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include "locmin.h"

#define debug(x) #x << " = " << x << '\n'
using ll = long long;
using i128 = __int128;

std::pair<int, int> find_locmin_point(int n, int m) {
    // daca a[1] < a[2] => e gata
    // daca a[n - 1] > a[n] => e gata
    // deci a[1] > a[2] si a[n - 1] < a[n]
    // caut binar mid

    if (n == 1) {
        if (m < 30) {
            std::vector<int> a(m);
            for (int i = 0; i < m; i++) {
                a[i] = value(1, i + 1);
            }
            a.insert(a.begin(), 0);
            if (a[1] < a[2]) {
                return {1, 1};
            }
            if (a[m] < a[m - 1]) {
                return {1, m};
            }
            for (int i = 2; i < m; i++) {
                if (a[i] < std::min(a[i - 1], a[i + 1])) {
                    return {1, i};
                }
            }
        }
        if (value(1, 1) < value(1, 2)) {
            return {1, 1};
        }
        if (value(1, m) < value(1, m - 1)) {
            return {1, m};
        }
        // am cv gen
        // >>><<><<<<>>><<<
        // >       <      <
        int l = 1, r = m;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            assert(1 <= mid && mid < m);
            assert(l < mid && mid < r);
            if (value(1, mid) < value(1, mid + 1)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return {1, l};
    } else {
        return {1, 1};
    }
}

/*

1 7
5 3 5 6 3 9 10



*/
