#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define cout(var) cout<<var<<endl
#define endl '\n'
#define loop(a,b,c) for(ll i=a;i<=b;i+=c)
#define intarr(arr,n) ll arr[n];for(ll i=0;i<n;i++)cin>>arr[i]
#define inparr(arr,n) for(ll i=0;i<n;i++)cin>>arr[i]
#define inpvec(vec,n) for(ll i=0;i<n;i++){ll var;cin>>var;vec.push_back(var);}
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define newline cout<<endl
#define ump unordered_map<ll,ll>
#define vec vector<ll>
#define mkp make_pair
#define disp(var) cout<<var<<" "
ll n;
ll bs=1357;
ll cnt=0;
ump f;
ll a[200005];
ll pvh[200005];
ll orig[200005];
vector<pair<pair<ll,ll>,ll>> upd;
struct query
{
ll l,r,i,up;
};
query qu[200005];
ll ans[200005];
vector<pair<ll,ll*>> compress;
bool comp(query a,query b)
{
if(a.l/bs!=b.l/bs)
{
return a.l/bs<b.l/bs;
}
if(a.r/bs!=b.r/bs)
return a.r<b.r;
return a.up<b.up;
}
bool comp1(pair<ll,ll*> aa,pair<ll,ll*> bb)
{
return aa.first<bb.first;
}
void add(ll pos)
{
ll ele=a[pos];
f[ele]++;
if(f[ele]==1)
cnt+=orig[ele];
}
void remove(ll pos)
{
//cout<<a[pos]<<endl;
ll ele=a[pos];
f[ele]--;
if(f[ele]==0)
cnt-=orig[ele];
}
void updatekaro(ll ct,ll left,ll right)
{
ll x=upd[ct].first.first;
ll oldvalue=a[x];
//cout<<x<<y<<oldvalue<<endl;
if(x>=left && x<=right)
{
f[oldvalue]--;
if(f[oldvalue]==0)
cnt-=orig[oldvalue];
}
a[x]=upd[ct].first.second;
ll y=a[x];
if(x>=left && x<=right)
{
f[y]++;
if(f[y]==1)
cnt+=orig[y];
}
}
void updatehatao(ll ct,ll left,ll right)
{
ll x=upd[ct].first.first;
ll oldvalue=a[x];
if(x>=left && x<=right)
{
f[oldvalue]--;
if(f[oldvalue]==0)
cnt-=orig[oldvalue];
}
a[x]=upd[ct].second;
ll y=a[x];
if(x>=left && x<=right)
{
f[y]++;
if(f[y]==1)
cnt+=orig[y];
}
}
void compression()
{
sort(compress.begin(),compress.end());
ll curr = compress[0].first;
ll idx = 0;
for(ll i = 0; i < compress.size(); i++)
{
if(curr != compress[i].first) idx++;
curr = compress[i].first;
orig[idx] = curr;
*compress[i].second = idx;
}
}
void AcDegaYe()
{
ll q;
cin>>n;
for(ll i=0;i<n;i++)
{
cin>>a[i];
pvh[i]=a[i];
compress.pb(mkp(a[i],&a[i]));
}
ll no;
ll updtillnow=0,x,y,in=0;
cin>>q;
for(ll i=0;i<q;i++)
{
char ch;
cin>>ch;
if(ch=='Q')
{
cin>>qu[in].l>>qu[in].r;
qu[in].l--;
qu[in].r--;
qu[in].i=in;
qu[in].up=updtillnow;
in++;
}
else
{
cin>>x>>y;
x--;
upd.pb(mkp(mkp(x,y),pvh[x]));
compress.pb(mkp(y,&y));
pvh[x]=y;
updtillnow++;
}
}
compression();
for(ll i=0;i<n;i++)
{
a[i]=compress[i].first;
pvh[i]=compress[i].first;
}
for(ll i=0;i<updtillnow;i++)
{
upd[i].first.second=compress[i].first;
upd[i].second=pvh[x];
pvh[x]=compress[i].first;
}
sort(qu,qu+in,comp);
ll ml=0,mr=-1,currenttime=0;
for(ll i=0;i<in;i++)
{
ll left=qu[i].l;
ll right=qu[i].r;
while(ml>left)
{
ml--;
add(ml);
}
while(mr<right)
{
mr++;
add(mr);
}
while(ml<left)
{
remove(ml);
ml++;
}
while(mr>right)
{
remove(mr);
mr--;
}
while(currenttime<qu[i].up)
{
updatekaro(currenttime,left,right);
currenttime++;
}
while(currenttime>qu[i].up)
{
updatehatao(currenttime-1,left,right);
currenttime--;
}
ans[qu[i].i]=cnt;
// for(ll i=0;i<n;i++)
// cout<<a[i]<<" ";
// cout<<endl;
}
for(ll i=0;i<in;i++)
{
cout(ans[i]);
}
}
int main()
{
fastio;
//ll t;
//cin>>t;
ll t=1;
while(t--)
{
AcDegaYe();
}
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7IAojZGVmaW5lIGxsIGxvbmcgbG9uZyBpbnQKI2RlZmluZSB1bGwgdW5zaWduZWQgbG9uZyBsb25nIGludAojZGVmaW5lIGxkIGxvbmcgZG91YmxlCiNkZWZpbmUgY291dCh2YXIpIGNvdXQ8PHZhcjw8ZW5kbAojZGVmaW5lIGVuZGwgJ1xuJwojZGVmaW5lIGxvb3AoYSxiLGMpIGZvcihsbCBpPWE7aTw9YjtpKz1jKQojZGVmaW5lIGludGFycihhcnIsbikgbGwgYXJyW25dO2ZvcihsbCBpPTA7aTxuO2krKyljaW4+PmFycltpXQojZGVmaW5lIGlucGFycihhcnIsbikgZm9yKGxsIGk9MDtpPG47aSsrKWNpbj4+YXJyW2ldCiNkZWZpbmUgaW5wdmVjKHZlYyxuKSBmb3IobGwgaT0wO2k8bjtpKyspe2xsIHZhcjtjaW4+PnZhcjt2ZWMucHVzaF9iYWNrKHZhcik7fQojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGZhc3RpbyBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKE5VTEwpOwojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CiNkZWZpbmUgbmV3bGluZSBjb3V0PDxlbmRsCiNkZWZpbmUgdW1wIHVub3JkZXJlZF9tYXA8bGwsbGw+CiNkZWZpbmUgdmVjIHZlY3RvcjxsbD4KI2RlZmluZSBta3AgbWFrZV9wYWlyCiNkZWZpbmUgZGlzcCh2YXIpIGNvdXQ8PHZhcjw8IiAiCmxsIG47CmxsIGJzPTEzNTc7CmxsIGNudD0wOwp1bXAgZjsKbGwgYVsyMDAwMDVdOwpsbCBwdmhbMjAwMDA1XTsKbGwgb3JpZ1syMDAwMDVdOwp2ZWN0b3I8cGFpcjxwYWlyPGxsLGxsPixsbD4+IHVwZDsKc3RydWN0IHF1ZXJ5CnsKICAgIGxsIGwscixpLHVwOwp9OwpxdWVyeSBxdVsyMDAwMDVdOwpsbCBhbnNbMjAwMDA1XTsKdmVjdG9yPHBhaXI8bGwsbGwqPj4gY29tcHJlc3M7Cgpib29sIGNvbXAocXVlcnkgYSxxdWVyeSBiKQp7CiAgICBpZihhLmwvYnMhPWIubC9icykKICAgIHsKICAgICAgICByZXR1cm4gYS5sL2JzPGIubC9iczsKICAgIH0KICAgIGlmKGEuci9icyE9Yi5yL2JzKQogICAgICAgIHJldHVybiBhLnI8Yi5yOwogICAgcmV0dXJuIGEudXA8Yi51cDsKfQpib29sIGNvbXAxKHBhaXI8bGwsbGwqPiBhYSxwYWlyPGxsLGxsKj4gYmIpCnsKICAgIHJldHVybiBhYS5maXJzdDxiYi5maXJzdDsKfQp2b2lkIGFkZChsbCBwb3MpCnsKICAgIGxsIGVsZT1hW3Bvc107CiAgICBmW2VsZV0rKzsKICAgIGlmKGZbZWxlXT09MSkKICAgICAgICBjbnQrPW9yaWdbZWxlXTsKfQp2b2lkIHJlbW92ZShsbCBwb3MpCnsKICAgIC8vY291dDw8YVtwb3NdPDxlbmRsOwogICAgbGwgZWxlPWFbcG9zXTsKICAgIGZbZWxlXS0tOwogICAgaWYoZltlbGVdPT0wKQogICAgICAgIGNudC09b3JpZ1tlbGVdOwp9CnZvaWQgdXBkYXRla2FybyhsbCBjdCxsbCBsZWZ0LGxsIHJpZ2h0KQp7CiAgICBsbCB4PXVwZFtjdF0uZmlyc3QuZmlyc3Q7CiAgICBsbCBvbGR2YWx1ZT1hW3hdOwogICAgLy9jb3V0PDx4PDx5PDxvbGR2YWx1ZTw8ZW5kbDsKICAgIGlmKHg+PWxlZnQgJiYgeDw9cmlnaHQpCiAgICB7CiAgICAgICAgZltvbGR2YWx1ZV0tLTsKICAgICAgICBpZihmW29sZHZhbHVlXT09MCkKICAgICAgICAgICAgY250LT1vcmlnW29sZHZhbHVlXTsKICAgIH0KICAgIGFbeF09dXBkW2N0XS5maXJzdC5zZWNvbmQ7CiAgICBsbCB5PWFbeF07CiAgICBpZih4Pj1sZWZ0ICYmIHg8PXJpZ2h0KQogICAgewogICAgICAgIGZbeV0rKzsKICAgICAgICBpZihmW3ldPT0xKQogICAgICAgICAgICBjbnQrPW9yaWdbeV07CiAgICB9Cn0Kdm9pZCB1cGRhdGVoYXRhbyhsbCBjdCxsbCBsZWZ0LGxsIHJpZ2h0KQp7CiAgICBsbCB4PXVwZFtjdF0uZmlyc3QuZmlyc3Q7CiAgICBsbCBvbGR2YWx1ZT1hW3hdOwogICAgaWYoeD49bGVmdCAmJiB4PD1yaWdodCkKICAgIHsKICAgICAgICBmW29sZHZhbHVlXS0tOwogICAgICAgIGlmKGZbb2xkdmFsdWVdPT0wKQogICAgICAgICAgICBjbnQtPW9yaWdbb2xkdmFsdWVdOwogICAgfQogICAgYVt4XT11cGRbY3RdLnNlY29uZDsKICAgIGxsIHk9YVt4XTsKICAgIGlmKHg+PWxlZnQgJiYgeDw9cmlnaHQpCiAgICB7CiAgICAgICAgZlt5XSsrOwogICAgICAgIGlmKGZbeV09PTEpCiAgICAgICAgICAgIGNudCs9b3JpZ1t5XTsKICAgIH0KCn0Kdm9pZCBjb21wcmVzc2lvbigpCnsKICAgIHNvcnQoY29tcHJlc3MuYmVnaW4oKSxjb21wcmVzcy5lbmQoKSk7CiAgICBsbCBjdXJyID0gY29tcHJlc3NbMF0uZmlyc3Q7CiAgICBsbCBpZHggPSAwOwogICAgZm9yKGxsIGkgPSAwOyBpIDwgY29tcHJlc3Muc2l6ZSgpOyBpKyspCiAgICB7CiAgICAgICAgaWYoY3VyciAhPSBjb21wcmVzc1tpXS5maXJzdCkgaWR4Kys7CiAgICAgICAgY3VyciA9IGNvbXByZXNzW2ldLmZpcnN0OwogICAgICAgIG9yaWdbaWR4XSA9IGN1cnI7CiAgICAgICAgKmNvbXByZXNzW2ldLnNlY29uZCA9IGlkeDsKICAgIH0KfQp2b2lkIEFjRGVnYVllKCkKewogICAgbGwgcTsKICAgIGNpbj4+bjsKICAgIGZvcihsbCBpPTA7aTxuO2krKykKICAgIHsKICAgICAgICBjaW4+PmFbaV07CiAgICAgICAgcHZoW2ldPWFbaV07CiAgICAgICAgY29tcHJlc3MucGIobWtwKGFbaV0sJmFbaV0pKTsKICAgIH0KICAgIGxsIG5vOwogICAgbGwgdXBkdGlsbG5vdz0wLHgseSxpbj0wOwogICAgY2luPj5xOwogICAgZm9yKGxsIGk9MDtpPHE7aSsrKQogICAgewogICAgICAgIGNoYXIgY2g7CiAgICAgICAgY2luPj5jaDsKICAgICAgICBpZihjaD09J1EnKQogICAgICAgIHsKICAgICAgICAgICAgY2luPj5xdVtpbl0ubD4+cXVbaW5dLnI7CiAgICAgICAgICAgIHF1W2luXS5sLS07CiAgICAgICAgICAgIHF1W2luXS5yLS07CiAgICAgICAgICAgIHF1W2luXS5pPWluOwogICAgICAgICAgICBxdVtpbl0udXA9dXBkdGlsbG5vdzsKICAgICAgICAgICAgaW4rKzsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgY2luPj54Pj55OwogICAgICAgICAgICB4LS07CiAgICAgICAgICAgIHVwZC5wYihta3AobWtwKHgseSkscHZoW3hdKSk7CiAgICAgICAgICAgIGNvbXByZXNzLnBiKG1rcCh5LCZ5KSk7CiAgICAgICAgICAgIHB2aFt4XT15OwogICAgICAgICAgICB1cGR0aWxsbm93Kys7CiAgICAgICAgfQogICAgfQogICAgY29tcHJlc3Npb24oKTsKICAgIGZvcihsbCBpPTA7aTxuO2krKykKICAgIHsKICAgICAgICBhW2ldPWNvbXByZXNzW2ldLmZpcnN0OwogICAgICAgIHB2aFtpXT1jb21wcmVzc1tpXS5maXJzdDsKICAgIH0KICAgIGZvcihsbCBpPTA7aTx1cGR0aWxsbm93O2krKykKICAgIHsKICAgICAgICB1cGRbaV0uZmlyc3Quc2Vjb25kPWNvbXByZXNzW2ldLmZpcnN0OwogICAgICAgIHVwZFtpXS5zZWNvbmQ9cHZoW3hdOwogICAgICAgIHB2aFt4XT1jb21wcmVzc1tpXS5maXJzdDsKICAgIH0KICAgIHNvcnQocXUscXUraW4sY29tcCk7CiAgICBsbCBtbD0wLG1yPS0xLGN1cnJlbnR0aW1lPTA7CiAgICBmb3IobGwgaT0wO2k8aW47aSsrKQogICAgewogICAgICAgIGxsIGxlZnQ9cXVbaV0ubDsKICAgICAgICBsbCByaWdodD1xdVtpXS5yOwogICAgICAgIHdoaWxlKG1sPmxlZnQpCiAgICAgICAgewogICAgICAgICAgICBtbC0tOwogICAgICAgICAgICBhZGQobWwpOwogICAgICAgIH0KICAgICAgICB3aGlsZShtcjxyaWdodCkKICAgICAgICB7CiAgICAgICAgICAgIG1yKys7CiAgICAgICAgICAgIGFkZChtcik7CiAgICAgICAgfQogICAgICAgIHdoaWxlKG1sPGxlZnQpCiAgICAgICAgewogICAgICAgICAgICByZW1vdmUobWwpOwogICAgICAgICAgICBtbCsrOwogICAgICAgIH0KICAgICAgICB3aGlsZShtcj5yaWdodCkKICAgICAgICB7CiAgICAgICAgICAgIHJlbW92ZShtcik7CiAgICAgICAgICAgIG1yLS07CiAgICAgICAgfQogICAgICAgIHdoaWxlKGN1cnJlbnR0aW1lPHF1W2ldLnVwKQogICAgICAgIHsKICAgICAgICAgICAgdXBkYXRla2FybyhjdXJyZW50dGltZSxsZWZ0LHJpZ2h0KTsKICAgICAgICAgICAgY3VycmVudHRpbWUrKzsKICAgICAgICB9CiAgICAgICAgd2hpbGUoY3VycmVudHRpbWU+cXVbaV0udXApCiAgICAgICAgewogICAgICAgICAgICB1cGRhdGVoYXRhbyhjdXJyZW50dGltZS0xLGxlZnQscmlnaHQpOwogICAgICAgICAgICBjdXJyZW50dGltZS0tOwogICAgICAgIH0KICAgICAgICBhbnNbcXVbaV0uaV09Y250OwogICAgLy8gICAgIGZvcihsbCBpPTA7aTxuO2krKykKICAgIC8vICAgICBjb3V0PDxhW2ldPDwiICI7CiAgICAvLyBjb3V0PDxlbmRsOwogICAgfQogICAgZm9yKGxsIGk9MDtpPGluO2krKykKICAgIHsKICAgICAgICBjb3V0KGFuc1tpXSk7CiAgICB9Cn0KIAppbnQgbWFpbigpCnsgICAKICAgIGZhc3RpbzsKICAgIC8vbGwgdDsKICAgIC8vY2luPj50OwogICAgbGwgdD0xOwogICAgd2hpbGUodC0tKQogICAgewogICAgICAgIEFjRGVnYVllKCk7CiAgICB9CiAgICBjZXJyIDw8ICJcblRpbWUgZWxhcHNlZDogIiA8PCAxMDAwICogY2xvY2soKSAvIENMT0NLU19QRVJfU0VDIDw8ICJtc1xuIjsKICAgIHJldHVybiAwOwp9