题解 | #【模板】二分#

#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <numeric>
#include <ctime>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;
const ll N = 1e5 + 5, mod = 1e9 + 7, inf = 2e18;

ll n, q, a[N];

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)cin >> a[i];

    while (q--) {
        int op, l, r, x;
        cin >> op >> l >> r >> x;
        l++;
        switch (op) {
            case 1: {
                    int idx = lower_bound(a + l, a + r + 1, x) - a;
                    if (idx >= l && idx <= r)cout << a[idx] << '\n';
                    else cout << -1 << '\n';
                    break;
                }
            case 2: {
                    int idx = upper_bound(a + l, a + r + 1, x) - a;
                    if (idx >= l && idx <= r)cout << a[idx] << '\n';
                    else cout << -1 << '\n';
                    break;
                }
            case 3: {
                    int idx = lower_bound(a + l, a + r + 1, x) - a - 1;
                    if (idx >= l && idx <= r)cout << a[idx] << '\n';
                    else cout << -1 << '\n';
                    break;
                }
            case 4: {
                    int idx = upper_bound(a + l, a + r + 1, x) - a - 1;
                    if (idx >= l && idx <= r)cout << a[idx] << '\n';
                    else cout << -1 << '\n';
                    break;
                }
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}