#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const double eps = 1e-15;
const double PI = atan(1.0);
#define readFile freopen("input","r",stdin)
#define writeFile freopen("output","w",stdout)
#define fastIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef pair<int,long long> ii;
typedef unsigned long long ULL;
const int N = 50003;
int inf = N;

struct xorShift{
private:
    ULL x,y,z,w;
public:
    xorShift(){
        x = 1,y=2,z=3,w=4;
    }
    ULL next(){
        ULL t = x^(x<<11);
        x = y,y=z,z=w;
        w = w^(w>>18)^t^(t>>9);
        return w = w^(w>>18)^t^(t>>9);
    }
};

xorShift gen = xorShift();

struct treap{
    int nxt;
    long long sz,val;
    ULL p;
    treap *l,*r;
    treap(){}
    treap(int nxtt,int val){
        this->nxt = nxtt;
        this->val = val;
        l = r = NULL;
        p = gen.next();
    }
};
#define pnode treap*

inline long long sz(pnode node){
    return node?node->sz:0;
}

inline void usz(pnode node){
    if (node)
        node->sz = sz(node->l)+sz(node->r)+node->val;
}

void split(pnode node,pnode &l,pnode &r,int key){
    if (!node) l = r = NULL;
    else if (node->nxt<=key) split(node->r,node->r,r,key),l = node;
    else split(node->l,l,node->l,key),r = node;
    usz(node);
}

void merge(pnode &node,pnode l,pnode r){
    if (!l||!r) node = l?l:r;
    else if (l->p>r->p) merge(l->r,l->r,r),node = l;
    else merge(r->l,l,r->l),node = r;
    usz(node);
}

void tinsert(pnode &node,int nxtt,int val,ULL p){
    if (!node){
        pnode temp = new treap(nxtt,val);
        temp->p = p;
        node = temp;
    }
    else if (node->nxt == nxtt) node->val+=val;
    else if (node->p<p){
        pnode temp = new treap(nxtt,val);
        temp->p = p;
        split(node,temp->l,temp->r,temp->nxt);
        node = temp;
    }
    else tinsert(node->nxt>nxtt?node->l:node->r,nxtt,val,p);
    usz(node);
}

void terase(pnode &node,int nxtt,int val){
    if (!node) return;
    if (node->nxt == nxtt){
        node->val -= val;
        if (!node->val){
            pnode temp = node;
            merge(node,node->l,node->r);
            free(temp);
        }
    }
    else terase(node->nxt>nxtt?node->l:node->r,nxtt,val);
    usz(node);
}

long long tquery(pnode &node,int val){
    pnode l; pnode r;
    split(node,l,r,val);
    long long res = sz(r);
    merge(node,l,r);
    return res;
}

pnode tree[N*4];

void insert(int node,int l,int r,int idx,int nxtt,int val){
    tinsert(tree[node],nxtt,val,gen.next());
    if (l==r) return;
    int mid = (l+r)>>1;
    if (idx<=mid) insert(node<<1,l,mid,idx,nxtt,val);
    else insert(node<<1|1,mid+1,r,idx,nxtt,val);
}

void update(int node,int l,int r,int idx,int nxtto,int valo,int nxtt,int val){
    terase(tree[node],nxtto,valo);
    tinsert(tree[node],nxtt,val,gen.next());
    if (l==r) return;
    int mid = (l+r)>>1;
    if (idx<=mid) update(node<<1,l,mid,idx,nxtto,valo,nxtt,val);
    else update(node<<1|1,mid+1,r,idx,nxtto,valo,nxtt,val);
}

long long query(int node,int l,int r,int ll,int rr){
    if (l>rr || r<ll) return 0;
    if (l>=ll && r<= rr) return tquery(tree[node],rr);
    int mid = (l+r)>>1;
    return query(node<<1,l,mid,ll,rr)+query(node<<1|1,mid+1,r,ll,rr);
}
int n,m,a,b;
ii arr[N];
int nxt[N],arr1[N];
map<int,set<int> > dict;
char c;

#define sit set<int>::iterator
#define mit map<int,set<int> >::iterator
inline void process1(int a){
    sit it = dict[arr1[a]].lower_bound(a);
    if (it!=dict[arr1[a]].begin()){
        it--;
        int idx = (*it);
        update(1,1,n,idx,nxt[idx],arr1[idx],nxt[a],arr1[idx]);
        nxt[idx] = nxt[a];
    }
}

inline void process(int a,int b){
    if (arr1[a]==b) return;
    process1(a);
    dict[arr1[a]].erase(a);
    dict[b].insert(a);
    mit dictb = dict.find(b);
    sit it = (*dictb).second.lower_bound(a);
    if (it!=dict[b].begin()){
        it--;
        int idx = (*it);
        int temp = nxt[idx];
        update(1,1,n,idx,nxt[idx],b,a,b);
        nxt[idx] = a;
        update(1,1,n,a,nxt[a],arr1[a],temp,b);
        nxt[a] = temp;
        arr1[a] = b;
        return;
    }
    it++;
    if (it!=dict[b].end()){
        int idx = (*it);
        update(1,1,n,a,nxt[a],arr1[a],idx,b);
        nxt[a] = idx;
        arr1[a] = b;
        return;
    }
    update(1,1,n,a,nxt[a],arr1[a],inf,b);
    nxt[a] = inf;
    arr1[a] = b;
}

int main(){
#ifndef ONLINE_JUDGE
    readFile;
    writeFile;
#endif
    fastIO;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>arr[i].first,arr[i].second = i,dict[arr[i].first].insert(i),arr1[i]=arr[i].first;
//        arr[i].first = gen.next()%n,arr[i].second = i,dict[arr[i].first].insert(i),arr1[i]=arr[i].first;
    memset(tree,NULL,sizeof(tree));
    sort(arr+1,arr+n+1);
    for(int i=1;i<=n-1;i++){
        if (arr[i].first==arr[i+1].first)
            nxt[arr[i].second] = arr[i+1].second;
        else nxt[arr[i].second] = inf;
    }
    nxt[arr[n].second] = inf;
    for(int i=1;i<=n;i++)
        insert(1,1,n,i,nxt[i],arr1[i]);
    cin>>m;
    while (m--){
        cin>>c>>a>>b;
        if (c=='Q') cout<<query(1,1,n,a,b)<<"\n";
        else process(a,b);
    }
}