#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const double eps = 1e-18;
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<long long,long long> ii;
typedef unsigned long long ULL;
const int N = 50005;
const int inf = 50002;

struct xorShift{
    ULL a,b,c,d;
    xorShift(){
        a = 1; b = 2; c = 3; d = 4;
    }
    ULL next(){
        ULL t = a^(a<<11);
        a = b; b = c; c = d;
        return d = d^(d>>19)^t^(t>>8);
    }
};
xorShift gen = xorShift();
struct treap{
    ii val;
    ULL p;
    long long sz;
    treap *l,*r;
    treap(){
        l = r = NULL;
    }
    treap(ii val){
        this->val = val;
        p = gen.next();
        l = r = NULL;
        sz = val.second;
    }
};

#define pnode treap*

pnode tree[N*4];
ii arr[N];
int nex[N],n,m,a,b;
long long arr1[N];
map<long long,set<int> > guide;
char c;
long long sz(pnode node){
    return node?node->sz:0;
}
void usz(pnode node){
    if (node)
        node->sz = sz(node->l)+sz(node->r)+node->val.second;
}

void split(pnode node,pnode &l,pnode &r, int key){
    if (!node) l = r = NULL;
    else if (node->val.first<=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,pnode ins){
    if (!node) node = ins;
    else if (node->p<ins->p){
        split(node,ins->l,ins->r,ins->val.first);
        node = ins;
    }
    else tinsert(node->val.first<=ins->val.first?node->r:node->l,ins);
    usz(node);
}
void terase(pnode &node,ii val){
    if (!node) return;
    if (node->val == val){
        pnode temp = node;
        merge(node,node->l,node->r);
        free(temp);
    }
    else if (node->val.first<val.first) terase(node->r,val);
    else terase(node->l,val);
    usz(node);
}
long long tquery(pnode node,int val){
    if (!node) return 0;
    if (node->val.first==val) return sz(node->r);
    if (node->val.first>val) return sz(node->r) + node->val.second+ tquery(node->l,val);
    return tquery(node->r,val);
}

void insert(int node,int l,int r,int idx,ii val){
    pnode temp = new treap(val);
    tinsert(tree[node],temp);
    if (l==r) return;
    int mid = (l+r)>>1;
    if (idx<=mid) insert(node<<1,l,mid,idx,val);
    else insert(node<<1|1,mid+1,r,idx,val);
}

void update(int node,int l,int r,int idx,ii old,ii val){
    pnode temp = new treap(val);
    terase(tree[node],old);
    tinsert(tree[node],temp);
    if (l==r) return;
    int mid = (l+r)>>1;
    if (idx<=mid) update(node<<1,l,mid,idx,old,val);
    else update(node<<1|1,mid+1,r,idx,old,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);
}
#define sit set<int>::iterator
#define mp(a,b) make_pair((a),(b))
void process(int a,long long b){
    sit it = guide[arr1[a]].lower_bound(a);
    if (it!= guide[arr1[1]].begin()) it--;
    if (it!=guide[arr1[a]].end() && (*it)<a){
        int idx = (*it);
        update(1,1,n,idx,mp(a,arr1[a]),mp(nex[a],arr1[a])),nex[idx] = nex[a];
    }
    it = guide[b].lower_bound(a);
    if (it!= guide[b].begin()) it--;
    if (it!=guide[b].end() && (*it)<a){
        int idx = (*it);
        update(1,1,n,idx,mp(nex[idx],b),mp(a,b));
        update(1,1,n,a,mp(nex[a],arr1[a]),mp(nex[idx],b));
        nex[a] = nex[idx];
        nex[idx] = a;
    }
    else{
        it = guide[b].upper_bound(a);
        if (it!=guide[b].end()){
            int idx = (*it);
            update(1,1,n,a,mp(nex[a],arr1[a]),mp(idx,b)),nex[a] = idx;
        }
        else update(1,1,n,a,mp(nex[a],arr1[a]),mp(inf,b)),nex[a] = inf;
    }
    guide[arr1[a]].erase(a);
    guide[b].insert(a);
    arr1[a] = b;
}



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