#pragma commet(linker, "/STACK:256000000")
#define _CRT_SECURE_NO_WARNINGS
#define FILEOUTPUT
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <limits.h>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <list>
#include <queue>
#include <string>
#include <memory>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cstdarg>
#include <cstdlib>
#include <cstdio>
#include <unordered_map>
using namespace std;
typedef int int_32;
#define int ll
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class T> void read_int(T& x){ cin >> x; }
template<class T, class ...Tail> void read_int(T& x, Tail&... tail){
    cin >> x;
    read_int(tail...);
}
template<class T> inline const T sqr(const T& x) {
    return x*x;
}
template<class T> inline bool isIn(const T& a, const T& b, const T& x) {
    return a <= x && x < b;
}
template<class T> const T binPow(T x, int n, T e){
    while (n){
        if (n & 1)
            e *= x;
        x *= x;
        n >>= 1;
    }
    return e;
}
template<class T> const T binPow(T x, int n, T e, int MOD){
    while (n){
        if (n & 1)
            e = (e*x) % MOD;
        x = (x*x) % MOD;
        n >>= 1;
    }
    return e;
}
#define in(...) int __VA_ARGS__; read_int(__VA_ARGS__)
#define iv(vec) for(int i = 0; i < vec.size(); cin >> vec[i++])
#define ov(vec, x) for(auto it = vec.begin(); it != vec.end(); cout << *it << x, ++it)
#define mp make_pair
#define all(vec) vec.begin(), vec.end()
#define so(vec) sort(all(vec))
#define re(vec) reverse(all(vec))
int bin_search(int left, int right, bool possibleFor(int)){
    int middle;
    while (left <= right){
        middle = (left + right) >> 1;
        if (possibleFor(middle))
            left = middle + 1;
        else
            right = middle - 1;
    }
    return right;
}
const int INF = 1e9 + 7;
const int LINF = sqr(INF - 7) + 7;
const ld EPS = 1e-13;
const string fileName = "different";
const string ProblemName = "last";
void run();
void save(){
    char k;
    ofstream saveTo(ProblemName + ".cpp");
    ifstream saveFrom("Source.cpp");
    while (saveFrom.get(k)) saveTo << k;
}
int_32 main(){
    ios_base::sync_with_stdio(0);
    cout << fixed << setprecision(13);
    cout.tie();
    cin.tie();
    srand(time(NULL));
#ifdef TRAINING
    save();
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#else
#ifdef FILEOUTPUT
    freopen((fileName + ".in").c_str(), "r", stdin);
    freopen((fileName + ".out").c_str(), "w", stdout);
#endif
#endif
    run();
    return 0;
}

class segment_tree{
    vector< pair<int,int> > treeMemory;
    const int realSize;
    void build(const vector<int>& v, int left, int right, int curr = 1){
        if (left == right){
            treeMemory[curr] = mp(v[left],0);
            return;
        }
        int middle = (left + right) >> 1;
        build(v, left, middle, curr << 1);
        build(v, middle + 1, right, (curr << 1) + 1);
        treeMemory[curr] = mp(max(treeMemory[curr << 1].first, treeMemory[(curr << 1) + 1].first), 0);
    }
    void push(int curr){
        treeMemory[curr << 1].second += treeMemory[curr].second;
        treeMemory[(curr << 1) + 1].second += treeMemory[curr].second;
        treeMemory[curr].second = 0;
    }
    void update(int value, int rl, int rr, int tl, int tr, int v = 1){
        if (rl > rr)
            return;
        if (rl == tl && rr == tr){
            treeMemory[v].second += value;
            return;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        update(value, rl, min(tm, rr), tl, tm, v << 1);
        update(value, max(rl, tm + 1), rr, tm + 1, tr, (v << 1) + 1);
        treeMemory[v].first = max(treeMemory[v << 1].second + treeMemory[v << 1].first, treeMemory[(v << 1) + 1].second + treeMemory[(v << 1) + 1].first);
    }
    const int get(int rl, int rr, int tl, int tr, int v = 1){
        if (rl > rr)
            return 0;
        if (rl == tl && rr == tr){
            return treeMemory[v].first + treeMemory[v].second;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        return max(
            get(rl, min(rr, tm), tl, tm, v << 1),
            get(max(rl, tm + 1), rr, tm + 1, tr, (v << 1) + 1)
            ) + treeMemory[v].second;
    }
public:
    segment_tree(const vector<int>& vecForTree) :treeMemory(vecForTree.size() << 2), realSize(vecForTree.size()){
        build(vecForTree, 0, realSize - 1);
    }
    const int operator()(int l, int r){
        return get(l, r, 0, realSize - 1);
    }
    const int operator[](int index){
        return operator()(index, index);
    }
    void treeUpdate(int v, int l, int r){
        update(v, l, r, 0, realSize - 1);
    }
};

pair<int, int> findMinimal(int v, set<int>& pos){
    auto it = pos.find(v);
    pair<int, int> res(-INF, INF);
    if (it != pos.begin()){
        --it;
        res.first = *it;
        ++it;
    }
    if (++it != pos.end()){
        res.second = *it;
    }
    return res;
}

void run(){
    in(n,m,k);
    vi vec(n);
    iv(vec);
    map<int, set<int> > poses;
    vi bucket(1000001, 0);
    vi vecForTree(n);
    int c = 0;
    for (int i = 0; i < k; ++i){
        if (bucket[vec[i]] == 0){
            ++c;
        }
        ++bucket[vec[i]];
        poses[vec[i]].insert(i);
        vecForTree[i] = c;
    }
    for (int i = k; i < n; ++i){
        if (bucket[vec[i - k]] == 1){
            --c;
        }
        --bucket[vec[i - k]];
        if (bucket[vec[i]] == 0){
            ++c;
        }
        ++bucket[vec[i]];
        poses[vec[i]].insert(i);
        vecForTree[i] = c;
    }
    segment_tree tree(vecForTree);
    int a, b;
    pair<int, int> upgradePos;
    for (int i = 0; i < m; ++i){
        cin >> c >> a >> b;
        --a;
        if (c == 1){
            set<int>& from = poses[vec[a]];
            set<int>& to = poses[b];

            upgradePos = findMinimal(a, from);
            upgradePos.first = max(a, upgradePos.first + k);
            upgradePos.second = min(n - 1, min(a + k - 1, upgradePos.second - 1));
            tree.treeUpdate(-1, upgradePos.first, upgradePos.second);
            from.erase(a);

            to.insert(a);
            upgradePos = findMinimal(a, to);
            upgradePos.first = max(a, upgradePos.first + k);
            upgradePos.second = min(n - 1, min(a + k - 1, upgradePos.second - 1));
            tree.treeUpdate(1, upgradePos.first, upgradePos.second);

            vec[a] = b;
        }
        else
            cout << tree(a + k - 1, b - 1) << endl;
    }

}