#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define llong long long
#define ld long double
#define endl '\n'


using namespace std;

const int N = 5e5 + 5;
const int M =  5*N + 5;
const int MOD = 1e9 + 7;
const int sz = 710;
const int rx[4] = {1, -1, 0, 0};
const int ry[4] = {0, 0, 1, -1};

int add[4*N], was[4 * N], a[N], t[N*4];



void push(int v, int sz) {
    if (was[v]) {
        was[v * 2] = 1;
        was[v * 2 + 1] = 1;
        add[v * 2] = add[v];
        add[v * 2 + 1] = add[v];
        t[v * 2] = add[v];
        t[v * 2 + 1] = add[v];
        add[v] = 0;
        was[v] = 0;
    }
}

void upd(int v, int cl, int cr, int l, int r, int x) {
    if (cl > r || cr < l) return;
    if (l <= cl && cr <= r) {
        add[v] = x;
        t[v] = (cr - cl + 1) * x;
        was[v] = 1;
        return;
    }
    int mid = (cr + cl) / 2;
    int sz = r - mid;
    push(v, sz);
    upd(v * 2, cl, mid, l, r, x);
    upd(v * 2 + 1, mid + 1, cr, l, r, x);
    t[v] = t[v * 2] + t[v * 2 + 1];
}

llong get(int v, int l, int r) {
    int mid = (r + l) / 2;
    int sz = r - mid;
    if (l == r) return l;
    push(v, sz);
    if (sz > t[v * 2]) {
        return get(v * 2, l, mid);
    } else {
        return get(v * 2 + 1, mid + 1, r);
    }
}

int32_t main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
#ifdef ARINOCHKA
    freopen("input.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
#else
//    freopen("substrcmp.in", "r", stdin);
//    freopen("substrcmp.out", "w", stdout);

#endif // ARINOCHKA


    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int p = 1;
    while(p < N) p *= 2;
//    for(int j = 0; j < n; j++) {
//        cout << a[j] << ' ';
//    }
//    cout << endl;

    for(int i = 0; i < m; i++) {
        int l, r;
        char c;
        cin >> c;
        if (c == '?') {
            cin >> l >> r;
            l--;
            r--;
            unordered_set <int> all;
            for(int j = l; j <= r; j++) {
                upd(1, 0, p - 1, a[j], a[j], 1);
            }
//            cout << l + 1 << ' ' << r + 1 << ": " << endl;
//            for(int j = l; j <= r; j++) {
//                cout << a[j] << ' ';
//            }
//            cout << endl;

            cout << get(1, 0, p - 1) << endl;
//            int k = 1;
//            int cur = 0;
//            for(int j = 1; j < p + p; j++){
//                cur++;
//                cout << t[j] << ' ';
//                if (cur == k){
//                    cout << endl;
//                    k *= 2;
//                    cur = 0;
//                }
//            }
//            cout << endl;
//            cout << endl;
            upd(1, 0, p - 1, 0, p - 1, 0);

        } else {
            int p, x;
            cin >> p >> x;
            p--;
            a[p] = x;
//            for(int j = 0; j < n; j++) {
//                cout << a[j] << ' ';
//            }
//            cout << endl;

        }
    }









    return 0;
}