#include <bits/stdc++.h>
#include <bits/extc++.h>
#include <tr2/dynamic_bitset>

#define int int64_t

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<typename T>
using orset = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using ormultiset = tree<T, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;

int32_t main()
{
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    map<int, orset<int>> cnt;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        a[i] = x;
        cnt[x].insert(i);
    }
    while(q--){
        int tp;
        cin >> tp;
        if(tp == 1){
            int i, x;
            cin >> i >> x;
            cnt[a[i]].erase(i);
            a[i] = x;
            cnt[a[i]].insert(i);
        }
        else{
            int l, r, cur = 0;
            cin >> l >> r;
            for(auto i: cnt){
                if(i.second.empty() || i.second.lower_bound(l) == i.second.end())
                    continue;
                int f = i.second.order_of_key(*i.second.lower_bound(l)), len;
                auto it = i.second.upper_bound(r);
                if(it == i.second.end()) {
                    len = i.second.size() - f;
                    if(*i.second.rbegin() > r || *i.second.rbegin() < l)
                        len--;
                }
                else
                    len = i.second.order_of_key(*it) - f;
                //cout << i.first << ' ' << f << ' ' << len << ' ' << *i.second.rbegin() << '\n';
                if(len & 1)
                    cur++;
            }
            cout << cur << '\n';
        }
    }
}