#include <iostream>
#include <set>
using namespace std;

set < int > onIds[(1<<20)];

struct vs {
    int l, r;
    int sum;
    vs () {
        l = -1;
        r = -1;
        sum = 0;
    }
}roots[(1<<24)];
int n, q, k = 18, lastAv = (1<<k)+1;

void addInd ( int ll, int rr, int x, int val, int crr ) {
    if ( ll == x && x+1 == rr ) { roots [ crr ].sum += val; return; }
    if ( x +1 <= ll || rr <= x ) { return; }

    if ( roots[crr].l == -1 ) {
        roots[crr].l = lastAv++;
        roots[crr].r = lastAv++;
    }
    addInd ( ll, (ll+rr)/2, x, val, roots[crr].l );
    addInd ( (ll+rr)/2, rr, x, val, roots[crr].r );

    roots[crr].sum = roots [ roots[crr].l ].sum + roots [ roots[crr].r ].sum;
}

void addElement ( int lPos, int rPos, int val ) {
    int ind = rPos+(1<<k);
    for ( ; ind ; ind /= 2 ) {
        addInd ( 0, (1<<k), lPos, val, ind );
    }
}

int getSum ( int l, int r, int ll, int rr, int crr ) {
    if ( crr == -1 ) { return 0; }
    if ( l <= ll && rr <= r ) { return roots[ crr].sum; }
    if ( rr <= l || r <= ll ) { return 0; }

    return getSum ( l, r, ll, (ll+rr)/2, roots[crr].l ) + getSum ( l, r, (ll+rr)/2, rr, roots[crr].r );
}


int getRoot ( int l, int r, int ll = 0, int rr = (1<<k), int ind = 1 ) {
    if ( l <= ll && rr <= r ) { return getSum( l, r, 0, (1<<k), ind ); }
    if ( rr <= l || r <= ll ) { return 0; }

    return getRoot ( l, r, ll, (ll+rr)/2, ind*2 ) + getRoot ( l, r, (ll+rr)/2, rr, ind*2+1 );
}
int arr[(1<<20)];

void rem ( int t, int i ) {

    auto rit = onIds[t].upper_bound( i ) ;
    auto lit = onIds[t].lower_bound ( i );

    int l = -1, r = -1;
    if ( rit != onIds[t].end() ) { r = *rit; }
    if ( lit != onIds[t].begin() ) { lit --; l = *lit; }

    if ( l != -1 ) {
        addElement( l, i, -(i-l) );
    }
    if ( r != -1 ) {
        addElement( i, r, -(r-i) );
    }

    if ( l != -1 && r != -1 ) {
        addElement( l, r, (r-l) );
    }

    onIds[t].erase ( i );
}

void add ( int t, int i ) {
    auto rit = onIds[t].upper_bound( i ) ;
    auto lit = onIds[t].upper_bound ( i );

    int l = -1, r = -1;
    if ( rit != onIds[t].end() ) { r = *rit; }
    if ( lit != onIds[t].begin() ) { lit --; l = *lit; }

    if ( l != -1 && r != -1 ) {
        addElement( l, r, -(r-l) );
    }

    if ( l != -1 ) {
        addElement( l, i, i-l );
    }
    if ( r != -1 ) {
        addElement( i, r, r-i );
    }

    onIds[t].insert( i );
}



int main () {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    for ( int i = 0 ; i < n ; i ++ ) {
        cin >> arr[i];
        if ( onIds[ arr[i] ].size() ) {
            auto lPos = onIds[ arr[i] ].end(); lPos --;
            addElement( *lPos, i, i-(*lPos) );
        }
        onIds[ arr[i] ].insert ( i );
    }

    for ( int i = 0 ; i < q ; i ++ ) {
        int t, l, r;
        cin >> t >> l >> r;
        if ( t == 1 ) {
            int ind = l-1, newT = r;

            rem( arr[ind], ind );
            add( newT, ind );

            arr[ind] = newT;

        }else {
            l --;
            cout << getRoot( l, r ) << "\n";
        }
    }


    return 0;
}
