#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using ll = long long;
#define DEBUG cout << "DEBUG\n";
#define eb emplace_back
#define em emplace
#define pii pair<int, int>
typedef long double ld;
using namespace std;
const ld PI = 3.14159265358979323L;

const int N = 5e5 + 7;
mt19937 rnd(time(0));

struct Treap {
    int nextInd, value, minValue;
    int y = rnd();
    Treap *l = nullptr;
    Treap *r = nullptr;
    Treap *p = nullptr;
    Treap(int value, int nextInd) : nextInd(nextInd), value(value), minValue(value) {}
};

int minValue(Treap *t) {
    if (t == nullptr) {
        return INT_MAX;
    }
    return t->minValue;
}

void update(Treap *t) {
    if (t == nullptr) {
        return;
    }
    t->minValue = min({minValue(t->r), minValue(t->l), t->value});
}

pair<Treap*, Treap*> split(Treap *t, int k) {
    if (t == nullptr) {
        return { nullptr, nullptr };
    }
    if (t->nextInd <= k) {
        auto q = split(t->r, k);
        t->r = q.first;
        update(t);
        return { t, q.second };
    }
    auto q = split(t->l, k);
    t->l = q.second;
    update(t);
    return { q.first, t };
}

Treap* merge(Treap *l, Treap *r) {
    if (l == nullptr) {
        return r;
    }
    if (r == nullptr) {
        return l;
    }
    if (l->y > r->y) {
        l->r = merge(l->r, r);
        update(l);
        return l;
    }
    r->l = merge(l, r->l);
    update(r);
    return r;
}

Treap* erase(Treap *t, int k) {
    if (t == nullptr) {
        return nullptr;
    }
    if (t->nextInd == k) {
        return merge(t->l, t->r);
    }
    if (t->nextInd > k) {
        t->l = erase(t->l, k);
    }
    else {
        t->r = erase(t->r, k);
    }
    update(t);
    return t;
}

Treap* add(Treap *t, Treap *toAdd) {
    auto q = split(t, toAdd->nextInd);
    t = merge(q.first, toAdd);
    t = merge(t, q.second);
    return t;
}

int n, m;
Treap *fenv[N], *lastTreap[N];
tuple<int, int, int> preBuild[3 * N];

void erase(int v, int toErase) {
    for (; v <= n; v |= v + 1) {
        fenv[v] = erase(fenv[v], toErase);
    }
}

void add(int v, int value, int nextInd) {
    for (; v <= n; v |= v + 1) {
        fenv[v] = add(fenv[v], new Treap(value, nextInd));
    }
}

int get(int v, int r) {
    v--;
    int ans = INT_MAX;
    for (; v >= 0; v = (v & (v + 1)) - 1) {
        auto q = split(fenv[v], r);
        ans = min(ans, minValue(q.second));
        fenv[v] = merge(q.first, q.second);
    }
    return ans;
}

void build(int v, int value, int nextInd) {
    for (; v <= n; v |= v + 1) {
        Treap *t = lastTreap[v];
        Treap *toAdd = new Treap(value, nextInd);
        lastTreap[v] = toAdd;
        if (t == nullptr) {
            fenv[v] = toAdd;
            continue;
        }
        if (t->y > toAdd->y) {
            t->r = toAdd;
            toAdd->p = t;
            update(t);
            continue;
        }
        while (t->p != nullptr && t->p->y < toAdd->y) {
            t = t->p;
        }
        if (t->p == nullptr) {
            toAdd->l = t;
            fenv[v] = toAdd;
            update(toAdd);
        }
        else {
            toAdd->l = t;
            t->p->r = toAdd;
            toAdd->p = t->p;
            update(toAdd);
            update(toAdd->p);
        }
    }
}

set<int> nums[N];
int arr[N];

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        nums[arr[i]].em(i);
    }
    for (int i = 0; i <= n; ++i) {
        fenv[i] = nullptr;
    }
    int actInd = 0;
    for (int i = 0; i <= n; ++i) {
        nums[i].em(0);
        nums[i].em(n + 1 + i);
        for (auto it = ++nums[i].rbegin(); it != nums[i].rend(); ++it) {
            int nextValue = *(--it);
            ++it;
            //add(*it, i, nextValue);
            preBuild[actInd++] = tuple<int, int, int>(nextValue, i, *it);
        }
    }
    sort(preBuild, preBuild + actInd);
    for (int i = 0; i < actInd; ++i) {
        int a, b, c;
        tie(a, b, c) = preBuild[i];
        build(c, b, a);
    }
    for (int i = 0; i < m; ++i) {
        char a;
        cin >> a;
        if (a == '?') {
            int l, r;
            cin >> l >> r;
            cout << get(l, r) << "\n";
        }
        else {
            int l, val;
            cin >> l >> val;
            erase(l, *nums[arr[l]].upper_bound(l));
            erase(*(--nums[arr[l]].lower_bound(l)), l);
            add(*(--nums[arr[l]].lower_bound(l)), arr[l], *nums[arr[l]].upper_bound(l));
            nums[arr[l]].erase(l);
            arr[l] = val;
            nums[val].em(l);
            erase(*(--nums[val].lower_bound(l)), *nums[val].upper_bound(l));
            add(*(--nums[val].lower_bound(l)), val, l);
            add(l, val, *nums[val].upper_bound(l));
        }
    }

    return 0;
}