DOshit

#include <iostream>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define len(v) (int)v.size()
#define all(v) v.begin(), v.end()
const int maxn = 1e5 + 10;
int inf = 1e6;
using namespace std;
using namespace __gnu_pbds;

vector<int> nxt(maxn, inf);
int a[maxn];
vector<int> frst(maxn, -1);

tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> t[maxn * 4];
void build(int v, int l, int r) {
    if (l + 1 == r) {
        tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> tmp;
        tmp.insert(nxt[l]);
        t[v] = tmp;
        return;
    }
    int m = (l + r) / 2;
    build(2 * v + 1, l, m);
    build(2 * v + 2, m, r);
    //t[v].insert();
    //t[v].insert(all(t[2 * v + 2]));
    //merge(all(t[2 * v + 1]), all(t[2 * v + 2]), t[v].begin());
    for (auto el : t[2 * v + 1])
        t[v].insert(el);
    for (auto el : t[2 * v + 2])
        t[v].insert(el);

}

void upd(int v, int l, int r, int pos, int x) {
    if (l + 1 == r) {
        tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> tmp;
        tmp.insert(x);
        t[v] = tmp;
    }
    int m = (l + r) / 2;
    if (pos < m)
        upd(2 * v + 1, l, m, pos, x);
    else
        upd(2 * v + 2, m, r, pos, x);
    t[v].clear();
    for (auto el : t[2 * v + 1])
        t[v].insert(el);
    for (auto el : t[2 * v + 2])
        t[v].insert(el);
}

ll get(int v, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return (len(t[v]) - t[v].order_of_key(qr));
    if (l >= qr || r <= ql) return 0;
    int m = (l + r) / 2;
    return get(2 * v + 1, l, m, ql, qr) + get(2 * v + 2, m, r, ql, qr);
}


int n, m;
void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (frst[a[i]] == -1) {
            frst[a[i]] = i;
        } else if (frst[a[i]] >= 1000000){
            nxt[frst[a[i]]] = i;
            frst[a[i]] = inf++;
        }
    }
    build(0, 0, n);
    while (m--) {
        int tp; cin >> tp;
        if (tp == 1) {
            int l, r; cin >> l >> r;
            --l;
            cout << get(0, 0, n, l, r) << endl;
        } else {
            int i, x; cin >> i >> x;
            --i;
            upd(0, 0, n, i, x);
        }
    }
}

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

    solve();
    return 0;
}