#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 bs=1375;
ll cnt=0;
ump f;
ll a[200005];
ll pvh[200005];
vector<pair<pair<ll,ll>,ll>> upd;
struct query
{
ll l,r,i,up;
};
query qu[200005];
ll ans[200005];
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;
}
void add(ll pos)
{
ll ele=a[pos];
f[ele]++;
if(f[ele]==1)
cnt+=ele;
}
void remove(ll pos)
{
//cout<<a[pos]<<endl;
ll ele=a[pos];
f[ele]--;
if(f[ele]==0)
cnt-=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-=oldvalue;
}
a[x]=upd[ct].first.second;
ll y=a[x];
if(x>=left && x<=right)
{
f[y]++;
if(f[y]==1)
cnt+=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-=oldvalue;
}
a[x]=upd[ct].second;
ll y=a[x];
if(x>=left && x<=right)
{
f[y]++;
if(f[y]==1)
cnt+=y;
}
}
void AcDegaYe()
{
ll n,q;
cin>>n;
for(ll i=0;i<n;i++)
{
cin>>a[i];
pvh[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]));
pvh[x]=y;
updtillnow++;
}
}
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+CiNkZWZpbmUgdmVjIHZlY3RvcjxsbD4KI2RlZmluZSBta3AgbWFrZV9wYWlyCiNkZWZpbmUgZGlzcCh2YXIpIGNvdXQ8PHZhcjw8IiAiCmxsIGJzPTEzNzU7CmxsIGNudD0wOwp1bXAgZjsKbGwgYVsyMDAwMDVdOwpsbCBwdmhbMjAwMDA1XTsKdmVjdG9yPHBhaXI8cGFpcjxsbCxsbD4sbGw+PiB1cGQ7CnN0cnVjdCBxdWVyeQp7CiAgICBsbCBsLHIsaSx1cDsKfTsKcXVlcnkgcXVbMjAwMDA1XTsKbGwgYW5zWzIwMDAwNV07CmJvb2wgY29tcChxdWVyeSBhLHF1ZXJ5IGIpCnsKICAgIGlmKGEubC9icyE9Yi5sL2JzKQogICAgewogICAgICAgIHJldHVybiBhLmwvYnM8Yi5sL2JzOwogICAgfQogICAgaWYoYS5yL2JzIT1iLnIvYnMpCiAgICAgICAgcmV0dXJuIGEucjxiLnI7CiAgICByZXR1cm4gYS51cDxiLnVwOwp9CnZvaWQgYWRkKGxsIHBvcykKewogICAgbGwgZWxlPWFbcG9zXTsKICAgIGZbZWxlXSsrOwogICAgaWYoZltlbGVdPT0xKQogICAgICAgIGNudCs9ZWxlOwp9CnZvaWQgcmVtb3ZlKGxsIHBvcykKewogICAgLy9jb3V0PDxhW3Bvc108PGVuZGw7CiAgICBsbCBlbGU9YVtwb3NdOwogICAgZltlbGVdLS07CiAgICBpZihmW2VsZV09PTApCiAgICAgICAgY250LT1lbGU7Cn0Kdm9pZCB1cGRhdGVrYXJvKGxsIGN0LGxsIGxlZnQsbGwgcmlnaHQpCnsKICAgIGxsIHg9dXBkW2N0XS5maXJzdC5maXJzdDsKICAgIGxsIG9sZHZhbHVlPWFbeF07CiAgICAvL2NvdXQ8PHg8PHk8PG9sZHZhbHVlPDxlbmRsOwogICAgaWYoeD49bGVmdCAmJiB4PD1yaWdodCkKICAgIHsKICAgICAgICBmW29sZHZhbHVlXS0tOwogICAgICAgIGlmKGZbb2xkdmFsdWVdPT0wKQogICAgICAgICAgICBjbnQtPW9sZHZhbHVlOwogICAgfQogICAgYVt4XT11cGRbY3RdLmZpcnN0LnNlY29uZDsKICAgIGxsIHk9YVt4XTsKICAgIGlmKHg+PWxlZnQgJiYgeDw9cmlnaHQpCiAgICB7CiAgICAgICAgZlt5XSsrOwogICAgICAgIGlmKGZbeV09PTEpCiAgICAgICAgICAgIGNudCs9eTsKICAgIH0KfQp2b2lkIHVwZGF0ZWhhdGFvKGxsIGN0LGxsIGxlZnQsbGwgcmlnaHQpCnsKICAgIGxsIHg9dXBkW2N0XS5maXJzdC5maXJzdDsKICAgIGxsIG9sZHZhbHVlPWFbeF07CiAgICBpZih4Pj1sZWZ0ICYmIHg8PXJpZ2h0KQogICAgewogICAgICAgIGZbb2xkdmFsdWVdLS07CiAgICAgICAgaWYoZltvbGR2YWx1ZV09PTApCiAgICAgICAgICAgIGNudC09b2xkdmFsdWU7CiAgICB9CiAgICBhW3hdPXVwZFtjdF0uc2Vjb25kOwogICAgbGwgeT1hW3hdOwogICAgaWYoeD49bGVmdCAmJiB4PD1yaWdodCkKICAgIHsKICAgICAgICBmW3ldKys7CiAgICAgICAgaWYoZlt5XT09MSkKICAgICAgICAgICAgY250Kz15OwogICAgfQoKfQp2b2lkIEFjRGVnYVllKCkKewogICAgbGwgbixxOwogICAgY2luPj5uOwogICAgZm9yKGxsIGk9MDtpPG47aSsrKQogICAgewogICAgICAgIGNpbj4+YVtpXTsKICAgICAgICBwdmhbaV09YVtpXTsKICAgIH0KICAgIGxsIG5vOwogICAgbGwgdXBkdGlsbG5vdz0wLHgseSxpbj0wOwogICAgY2luPj5xOwogICAgZm9yKGxsIGk9MDtpPHE7aSsrKQogICAgewogICAgICAgIGNoYXIgY2g7CiAgICAgICAgY2luPj5jaDsKICAgICAgICBpZihjaD09J1EnKQogICAgICAgIHsKICAgICAgICAgICAgY2luPj5xdVtpbl0ubD4+cXVbaW5dLnI7CiAgICAgICAgICAgIHF1W2luXS5sLS07CiAgICAgICAgICAgIHF1W2luXS5yLS07CiAgICAgICAgICAgIHF1W2luXS5pPWluOwogICAgICAgICAgICBxdVtpbl0udXA9dXBkdGlsbG5vdzsKICAgICAgICAgICAgaW4rKzsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgY2luPj54Pj55OwogICAgICAgICAgICB4LS07CiAgICAgICAgICAgIHVwZC5wYihta3AobWtwKHgseSkscHZoW3hdKSk7CiAgICAgICAgICAgIHB2aFt4XT15OwogICAgICAgICAgICB1cGR0aWxsbm93Kys7CiAgICAgICAgfQogICAgfQogICAgc29ydChxdSxxdStpbixjb21wKTsKICAgIGxsIG1sPTAsbXI9LTEsY3VycmVudHRpbWU9MDsKICAgIGZvcihsbCBpPTA7aTxpbjtpKyspCiAgICB7CiAgICAgICAgbGwgbGVmdD1xdVtpXS5sOwogICAgICAgIGxsIHJpZ2h0PXF1W2ldLnI7CiAgICAgICAgd2hpbGUobWw+bGVmdCkKICAgICAgICB7CiAgICAgICAgICAgIG1sLS07CiAgICAgICAgICAgIGFkZChtbCk7CiAgICAgICAgfQogICAgICAgIHdoaWxlKG1yPHJpZ2h0KQogICAgICAgIHsKICAgICAgICAgICAgbXIrKzsKICAgICAgICAgICAgYWRkKG1yKTsKICAgICAgICB9CiAgICAgICAgd2hpbGUobWw8bGVmdCkKICAgICAgICB7CiAgICAgICAgICAgIHJlbW92ZShtbCk7CiAgICAgICAgICAgIG1sKys7CiAgICAgICAgfQogICAgICAgIHdoaWxlKG1yPnJpZ2h0KQogICAgICAgIHsKICAgICAgICAgICAgcmVtb3ZlKG1yKTsKICAgICAgICAgICAgbXItLTsKICAgICAgICB9CiAgICAgICAgd2hpbGUoY3VycmVudHRpbWU8cXVbaV0udXApCiAgICAgICAgewogICAgICAgICAgICB1cGRhdGVrYXJvKGN1cnJlbnR0aW1lLGxlZnQscmlnaHQpOwogICAgICAgICAgICBjdXJyZW50dGltZSsrOwogICAgICAgIH0KICAgICAgICB3aGlsZShjdXJyZW50dGltZT5xdVtpXS51cCkKICAgICAgICB7CiAgICAgICAgICAgIHVwZGF0ZWhhdGFvKGN1cnJlbnR0aW1lLTEsbGVmdCxyaWdodCk7CiAgICAgICAgICAgIGN1cnJlbnR0aW1lLS07CiAgICAgICAgfQogICAgICAgIGFuc1txdVtpXS5pXT1jbnQ7CiAgICAvLyAgICAgZm9yKGxsIGk9MDtpPG47aSsrKQogICAgLy8gICAgIGNvdXQ8PGFbaV08PCIgIjsKICAgIC8vIGNvdXQ8PGVuZGw7CiAgICB9CiAgICBmb3IobGwgaT0wO2k8aW47aSsrKQogICAgewogICAgICAgIGNvdXQoYW5zW2ldKTsKICAgIH0KfQogCmludCBtYWluKCkKeyAgIAogICAgZmFzdGlvOwogICAgLy9sbCB0OwogICAgLy9jaW4+PnQ7CiAgICBsbCB0PTE7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgQWNEZWdhWWUoKTsKICAgIH0KICAgIGNlcnIgPDwgIlxuVGltZSBlbGFwc2VkOiAiIDw8IDEwMDAgKiBjbG9jaygpIC8gQ0xPQ0tTX1BFUl9TRUMgPDwgIm1zXG4iOwogICAgcmV0dXJuIDA7Cn0=