// 2018, Sayutin Dmitry.

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

#define pb push_back
#define eb emplace_back


template <size_t buf_sz>
struct in_reader {
    in_reader(FILE* f): f(f) {}

    void set_err() {
        err = true;
#ifdef LOCAL
        assert(false);
#endif
    }

    int peekch() {
        if (term)
            return EOF;
        else if (l == r and r == buf_sz) {
            l = 0;
            r = fread(buf, 1, buf_sz, f);
        }

        if (l != r)
            return buf[l];
        else {
            term = true;
            if (ferror(f))
                set_err();
            return EOF;
        }
    }

    int getch() {
        int res = peekch();
        if (res != EOF)
            ++l;
        return res;
    }

    void seek_token() {
        while (peekch() != EOF and std::isspace(peekch()))
            getch();
    }

    template <typename T>
    T input_int() {
        seek_token();

        if (peekch() == EOF)
            set_err();

        char ch = peekch();
        bool positive = true;
        if (ch == '+')
            getch();
        else if (ch == '-')
            getch(), positive = false;
        else if (not ('0' <= ch and ch <= '9')) {
            set_err();
            return 0;
        }

        int num_read = 0;
        T res = 0;
        while ('0' <= peekch() and peekch() <= '9')
            res = 10 * res + getch() - '0', ++num_read;

        if (num_read == 0)
            set_err();
        if (positive == false and res > 0 and not std::numeric_limits<T>::is_signed)
            set_err();
        if (positive == false)
            res = -res;
        return res;
    }

    std::string input_string() {
        seek_token();

        std::string res;
        while (peekch() != EOF and not std::isspace(peekch()))
            res += getch();
        return res;
    }

    template <typename T>
    T input_float() {
        seek_token();
        size_t tmp_sz = 0;

        if (peekch() == '+' or peekch() == '-')
            tmp[tmp_sz++] = getch();
        while ('0' <= peekch() and peekch() <= '9' and tmp_sz != 60)
            tmp[tmp_sz++] = getch();
        if (peekch() == '.' and tmp_sz != 60) {
            tmp[tmp_sz++] = getch();
            while ('0' <= peekch() and peekch() <= '9' and tmp_sz != 60)
                tmp[tmp_sz++] = getch();
        }

        if (tmp_sz == 60 or tmp_sz == 0) {
            set_err();
            return 0;
        }
        tmp[tmp_sz] = 0;
        if (std::is_same<T, float>::value)
            return strtof(tmp, NULL);
        else if (std::is_same<T, double>::value)
            return strtod(tmp, NULL);
        else if (std::is_same<T, long double>::value)
            return strtold(tmp, NULL);
        else {
            set_err();
            return 0;
        }
    }

    void input_string_to(char* out, size_t mx) {
        seek_token();
        mx -= 1;

        while (peekch() != EOF and not std::isspace(peekch()) and mx != 0)
            *(out++) = getch(), --mx;
        *out = 0;
    }

    char tmp[60];
    char buf[buf_sz];
    FILE* f;
    size_t l = buf_sz;
    size_t r = buf_sz;
    bool term = false;
    bool err  = false;
};


template <size_t buf_sz>
struct out_writer {
    out_writer(FILE* f): f(f) {}
    ~out_writer() {flush();}

    void set_err() {
        err = true;
#ifdef LOCAL
        assert(false);
#endif
    }

    void flush() {
        if (pos == 0)
            return;

        if (fwrite(buf, 1, pos, f) != pos)
            set_err();
        pos = 0;
    }

    void putch(char ch) {
        if (pos == buf_sz)
            flush();
        buf[pos++] = ch;
    }

    template <typename T>
    void write_int(T elem) {
        if (elem < 0) {
            putch('-');
            elem = -elem;
        }

        size_t tmp_sz = 0;
        while (elem != 0)
            tmp[tmp_sz++] = '0' + elem % 10, elem /= 10;

        if (tmp_sz == 0)
            putch('0');
        else
            while (tmp_sz != 0)
                putch(tmp[--tmp_sz]);
    }

    void write_string(const std::string& str) {
        write_string_raw(str.data());
    }

    template <typename T>
    void write_float(T v) {
        if (std::is_same<T, float>::value)
            snprintf(tmp, 60, "%.7f", v);
        else if (std::is_same<T, double>::value)
            snprintf(tmp, 60, "%.7lf", v);
        else if (std::is_same<T, long double>::value)
            snprintf(tmp, 60, "%.7Lf", v);
        else {
            set_err();
        }
        write_string_raw(tmp);
    }

    void write_string_raw(const char* out) {
        while (*out != 0)
            putch(*(out++));
    }

    char tmp[60];
    char buf[buf_sz];
    FILE* f;
    size_t pos = 0;
    bool err = false;
};

in_reader<4096> reader(stdin);
out_writer<4096> writer(stdout);


struct fast_t {
    vector<tuple<int, int, int>> evs;
    // add :: 0 r val
    // del :: 1 r val
    // que :: 2 min_r p_ans

    void add(int r, int val) {
        evs.emplace_back(0, r, val);
    }

    void rem(int r, int val) {
        evs.emplace_back(1, r, val);
    }

    void get_ans(int r, int p_ans) {
        evs.emplace_back(2, r, p_ans);
    }

    void solve(vector<int>& answers) {
        vector<pair<int, int>> vals;
        for (auto elem: evs)
            if (get<0>(elem) == 0)
                vals.emplace_back(get<1>(elem), get<2>(elem));

        std::sort(ALL(vals));
        vals.resize(std::unique(ALL(vals)) - vals.begin());

        if (vals.empty())
            return;

        int sz = 1;
        while (sz < SZ(vals))
            sz *= 2;

        int tree[2 * sz];
        std::fill(tree, tree + 2 * sz, TYPEMAX(int));

        auto get_ind = [&](int r, int val) {
            return std::lower_bound(ALL(vals), make_pair(r, val)) - vals.begin();
        };

        for (auto elem: evs) {
            if (get<0>(elem) == 0) {
                int i = get_ind(get<1>(elem), get<2>(elem));

                tree[sz + i] = get<2>(elem);

                for (int j = (sz + i) / 2; j >= 1; j = j / 2)
                    tree[j] = min(tree[2 * j], tree[2 * j + 1]);
            } else if (get<0>(elem) == 1) {
                int i = get_ind(get<1>(elem), get<2>(elem));

                tree[sz + i] = TYPEMAX(int);

                for (int j = (sz + i) / 2; j >= 1; j = j / 2)
                    tree[j] = min(tree[2 * j], tree[2 * j + 1]);
            } else {
                int i = sz + get_ind(get<1>(elem), -1000);
                int j = 2 * sz - 1;

                int p_ans = get<2>(elem);

                while (i <= j) {
                    if (i % 2 == 1)
                        answers[p_ans] = min(answers[p_ans], tree[i]), ++i;
                    if (j % 2 == 0)
                        answers[p_ans] = min(answers[p_ans], tree[j]), --j;

                    i /= 2;
                    j /= 2;
                }
            }
        }
    }
};

int main() {
    // code here

    int n = reader.input_int<int>();
    int q = reader.input_int<int>();
    vector<int> a(n);

    vector<set<int>> where(n + 5);

    for (int i = 0; i != n; ++i) {
        a[i] = reader.input_int<int>();

        if (a[i] < SZ(where))
            where[a[i]].insert(i);
    }

    vector<fast_t> fenw(n);

    auto add = [&](int l, int r, int val) {
        for (; l < n; l = l | (l + 1)) {
            fenw[l].add(r, val);
        }
    };

    auto del = [&](int l, int r, int val) {
        for (; l < n; l = l | (l + 1)) {
            fenw[l].rem(r, val);
        }
    };

    for (int i = 0; i < SZ(where); ++i) {
        int start = 0;

        for (int elem: where[i]) {
            if (start <= elem - 1)
                add(start, elem - 1, i);
            start = elem + 1;
        }

        if (start <= n - 1)
            add(start, n - 1, i);
    }

    vector<int> answers;

    for (int iter = 0; iter != q; ++iter) {
        reader.seek_token();
        if (reader.getch() == '!') {
            int i = reader.input_int<int>() - 1;
            int x = reader.input_int<int>();

            if (a[i] < SZ(where)) {
                auto it = where[a[i]].find(i);

                int prev = (it == where[a[i]].begin() ? -1 : *std::prev(it));
                int next = (std::next(it) == where[a[i]].end() ? n : *std::next(it));

                if (prev + 1 <= i - 1)
                    del(prev + 1, i - 1, a[i]);

                if (i + 1 <= next - 1)
                    del(i + 1, next - 1, a[i]);

                add(prev + 1, next - 1, a[i]);
                where[a[i]].erase(it);
            }

            a[i] = x;

            if (a[i] < SZ(where)) {
                auto it = where[a[i]].insert(i).first;

                int prev = (it == where[a[i]].begin() ? -1 : *std::prev(it));
                int next = (std::next(it) == where[a[i]].end() ? n : *std::next(it));

                if (prev + 1 <= next - 1)
                    del(prev + 1, next - 1, a[i]);

                if (prev + 1 <= i - 1)
                    add(prev + 1, i - 1, a[i]);

                if (i + 1 <= next - 1)
                    add(i + 1, next - 1, a[i]);
            }
        } else {
            int l = reader.input_int<int>() - 1;
            int r = reader.input_int<int>() - 1;

            answers.push_back(TYPEMAX(int));
            for (; l >= 0; l = (l & (l + 1)) - 1) {
                fenw[l].get_ans(r, SZ(answers) - 1);
            }
        }
    }

    for (auto& elem: fenw)
        elem.solve(answers);

    for (auto elem: answers) {
        writer.write_int(elem);
        writer.putch('\n');
    }

    return 0;
}