#include <bits/stdc++.h>
using namespace std;
struct node {
int prior, size, pos;
int val, sum;
node *l, *r;
};
typedef node* pnode;
int sz(pnode t) {
return t ? t->size : 0;
}
void upd_sz(pnode t) {
if(t) {
t->size = sz(t->l) + sz(t->r) + 1;
}
}
void combine(pnode &t, pnode l, pnode r) {
if(!l || !r) {
t = l ? l : r;
return;
}
t->sum = l->sum + r->sum;
}
void reset(pnode t) {
if(t) {
t->sum = t->val;
}
}
void operation(pnode t) {
if(!t) {
return;
}
reset(t);
combine(t, t->l, t);
combine(t, t, t->r);
}
void split(pnode t, pnode &l, pnode &r, int pos) {
if(!t) {
l = r = NULL;
return;
}
if(t->pos <= pos) {
split(t->r, t->r, r, pos);
l = t;
}
else {
split(t->l, l, t->l, pos);
r = t;
}
upd_sz(t);
operation(t);
}
void merge(pnode &t, pnode l, pnode r) {
if(!l || !r) {
t = l ? l : r;
}
else if(l->prior > r->prior) {
merge(l->r, l->r, r);
t = l;
}
else {
merge(r->l, l, r->l);
t = r;
}
upd_sz(t);
operation(t);
}
void init(pnode &t, int pos = -1, int val = 0) {
t->prior = rand();
t->pos = pos;
t->size = 1;
t->val = val;
t->sum = t->val;
t->l = t->r = NULL;
}
const int N = 1e5 + 10;
pnode seg[N << 2];
int A[N];
int Left[N];
int get_sum(pnode t, int pos) {
pnode l, r;
split(t, l, r, pos);
int ans = l ? l->sum : 0;
merge(t, l, r);
return ans;
}
void update(int l, int r, int id, int pos, int old_val, int val, int old_pos, int new_pos) {
pnode L, mid, R;
if(old_pos > -1) {
split(seg[id], L, mid, old_pos-1);
split(mid, seg[id], R, old_pos);
if(seg[id]) {
seg[id]->val -= old_val;
seg[id]->sum -= old_val;
}
merge(mid, L, seg[id]);
merge(seg[id], mid, R);
}
split(seg[id], L, mid, new_pos-1);
split(mid, seg[id], R, new_pos);
if(seg[id]) {
seg[id]->val += val;
seg[id]->sum += val;
}
else {
seg[id] = new node;
init(seg[id], new_pos, val);
}
merge(mid, L, seg[id]);
merge(seg[id], mid, R);
if(l == r) {
return;
}
int _mid = l + r >> 1;
if(_mid >= pos)
update(l, _mid, id << 1, pos, old_val, val, old_pos, new_pos);
else
update(_mid + 1, r, id << 1 | 1, pos, old_val, val, old_pos, new_pos);
}
int query(int l, int r, int id, int x, int y) {
if(l > y || r < x)
return 0;
if(l >= x && r <= y) {
return get_sum(seg[id], x - 1);
}
int mid = l + r >> 1;
return query(l, mid, id << 1, x, y) + query(mid + 1, r, id << 1 | 1, x, y);
}
map < int, set < int > > M;
int main() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", A + i);
M[A[i]].insert(0);
auto it = M[A[i]].end();
--it;
Left[i] = *it;
M[A[i]].insert(i);
}
for(int i = 1; i <= n; ++i) {
update(1, n, 1, i, 0, A[i], -1, Left[i]);
}
int q;
scanf("%d", &q);
for(int i = 1; i <= q; ++i) {
char c;
int x, y;
scanf(" %c %d %d", &c, &x, &y);
if(c == 'Q') {
int ans = query(1, n, 1, x, y);
printf("%d\n", ans);
}
else if(A[x] != y) {
M[y].insert(0);
auto it = M[y].lower_bound(x);
auto it3 = M[A[x]].upper_bound(x);
auto it2 = it;
--it;
update(1, n, 1, x, A[x], y, Left[x], *it);
if(it2 != M[y].end()) {
update(1, n, 1, *it2, y, y, Left[*it2], x);
Left[*it2] = x;
}
if(it3 != M[A[x]].end()) {
update(1, n, 1, *it3, A[x], A[x], x, Left[x]);
Left[*it3] = Left[x];
}
M[y].insert(x);
M[A[x]].erase(x);
A[x] = y;
Left[x] = *it;
}
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3Qgbm9kZSB7CglpbnQgcHJpb3IsIHNpemUsIHBvczsKCWludCB2YWwsIHN1bTsKCW5vZGUgKmwsICpyOwp9Owp0eXBlZGVmIG5vZGUqIHBub2RlOwoKaW50IHN6KHBub2RlIHQpIHsKCXJldHVybiB0ID8gdC0+c2l6ZSA6IDA7Cn0KCnZvaWQgdXBkX3N6KHBub2RlIHQpIHsKCWlmKHQpIHsKCQl0LT5zaXplID0gc3oodC0+bCkgKyBzeih0LT5yKSArIDE7Cgl9Cn0KCnZvaWQgY29tYmluZShwbm9kZSAmdCwgcG5vZGUgbCwgcG5vZGUgcikgewoJaWYoIWwgfHwgIXIpIHsKCQl0ID0gbCA/IGwgOiByOwoJCXJldHVybjsKCX0KCXQtPnN1bSA9IGwtPnN1bSArIHItPnN1bTsKfQoKdm9pZCByZXNldChwbm9kZSB0KSB7CglpZih0KSB7CgkJdC0+c3VtID0gdC0+dmFsOwoJfQp9Cgp2b2lkIG9wZXJhdGlvbihwbm9kZSB0KSB7CglpZighdCkgewoJCXJldHVybjsKCX0KCXJlc2V0KHQpOwoJY29tYmluZSh0LCB0LT5sLCB0KTsKCWNvbWJpbmUodCwgdCwgdC0+cik7Cn0KCnZvaWQgc3BsaXQocG5vZGUgdCwgcG5vZGUgJmwsIHBub2RlICZyLCBpbnQgcG9zKSB7CglpZighdCkgewoJCWwgPSByID0gTlVMTDsKCQlyZXR1cm47Cgl9CgoJaWYodC0+cG9zIDw9IHBvcykgewoJCXNwbGl0KHQtPnIsIHQtPnIsIHIsIHBvcyk7CgkJbCA9IHQ7Cgl9CgllbHNlIHsKCQlzcGxpdCh0LT5sLCBsLCB0LT5sLCBwb3MpOwoJCXIgPSB0OwoJfQoJdXBkX3N6KHQpOwoJb3BlcmF0aW9uKHQpOwp9Cgp2b2lkIG1lcmdlKHBub2RlICZ0LCBwbm9kZSBsLCBwbm9kZSByKSB7CglpZighbCB8fCAhcikgewoJCXQgPSBsID8gbCA6IHI7Cgl9CgllbHNlIGlmKGwtPnByaW9yID4gci0+cHJpb3IpIHsKCQltZXJnZShsLT5yLCBsLT5yLCByKTsKCQl0ID0gbDsKCX0KCWVsc2UgewoJCW1lcmdlKHItPmwsIGwsIHItPmwpOwoJCXQgPSByOwoJfQoJdXBkX3N6KHQpOwoJb3BlcmF0aW9uKHQpOwp9Cgp2b2lkIGluaXQocG5vZGUgJnQsIGludCBwb3MgPSAtMSwgaW50IHZhbCA9IDApIHsKCXQtPnByaW9yID0gcmFuZCgpOwoJdC0+cG9zID0gcG9zOwoJdC0+c2l6ZSA9IDE7Cgl0LT52YWwgPSB2YWw7Cgl0LT5zdW0gPSB0LT52YWw7Cgl0LT5sID0gdC0+ciA9IE5VTEw7Cn0KCmNvbnN0IGludCBOID0gMWU1ICsgMTA7CnBub2RlIHNlZ1tOIDw8IDJdOwppbnQgQVtOXTsKaW50IExlZnRbTl07CgppbnQgZ2V0X3N1bShwbm9kZSB0LCBpbnQgcG9zKSB7Cglwbm9kZSBsLCByOwoJc3BsaXQodCwgbCwgciwgcG9zKTsKCWludCBhbnMgPSBsID8gbC0+c3VtIDogMDsKCW1lcmdlKHQsIGwsIHIpOwoJcmV0dXJuIGFuczsKfQoKdm9pZCB1cGRhdGUoaW50IGwsIGludCByLCBpbnQgaWQsIGludCBwb3MsIGludCBvbGRfdmFsLCBpbnQgdmFsLCBpbnQgb2xkX3BvcywgaW50IG5ld19wb3MpIHsKCXBub2RlIEwsIG1pZCwgUjsKCWlmKG9sZF9wb3MgPiAtMSkgewoJCXNwbGl0KHNlZ1tpZF0sIEwsIG1pZCwgb2xkX3Bvcy0xKTsKCQlzcGxpdChtaWQsIHNlZ1tpZF0sIFIsIG9sZF9wb3MpOwoKCQlpZihzZWdbaWRdKSB7CgkJCXNlZ1tpZF0tPnZhbCAtPSBvbGRfdmFsOwoJCQlzZWdbaWRdLT5zdW0gLT0gb2xkX3ZhbDsKCQl9CgoJCW1lcmdlKG1pZCwgTCwgc2VnW2lkXSk7CgkJbWVyZ2Uoc2VnW2lkXSwgbWlkLCBSKTsKCX0KCgoJc3BsaXQoc2VnW2lkXSwgTCwgbWlkLCBuZXdfcG9zLTEpOwoJc3BsaXQobWlkLCBzZWdbaWRdLCBSLCBuZXdfcG9zKTsKCglpZihzZWdbaWRdKSB7CgkJc2VnW2lkXS0+dmFsICs9IHZhbDsKCQlzZWdbaWRdLT5zdW0gKz0gdmFsOwoJfQoJZWxzZSB7CgkJc2VnW2lkXSA9IG5ldyBub2RlOwoJCWluaXQoc2VnW2lkXSwgbmV3X3BvcywgdmFsKTsKCX0KCQoJbWVyZ2UobWlkLCBMLCBzZWdbaWRdKTsKCW1lcmdlKHNlZ1tpZF0sIG1pZCwgUik7CgoJaWYobCA9PSByKSB7CgkJcmV0dXJuOwoJfQkKCQoJaW50IF9taWQgPSBsICsgciA+PiAxOwoJaWYoX21pZCA+PSBwb3MpCgkJdXBkYXRlKGwsIF9taWQsIGlkIDw8IDEsIHBvcywgb2xkX3ZhbCwgdmFsLCBvbGRfcG9zLCBuZXdfcG9zKTsKCWVsc2UKCQl1cGRhdGUoX21pZCArIDEsIHIsIGlkIDw8IDEgfCAxLCBwb3MsIG9sZF92YWwsIHZhbCwgb2xkX3BvcywgbmV3X3Bvcyk7Cn0KCmludCBxdWVyeShpbnQgbCwgaW50IHIsIGludCBpZCwgaW50IHgsIGludCB5KSB7CglpZihsID4geSB8fCByIDwgeCkJCgkJcmV0dXJuIDA7CglpZihsID49IHggJiYgciA8PSB5KSB7CgkJcmV0dXJuIGdldF9zdW0oc2VnW2lkXSwgeCAtIDEpOwoJfQoJaW50IG1pZCA9IGwgKyByID4+IDE7CglyZXR1cm4gcXVlcnkobCwgbWlkLCBpZCA8PCAxLCB4LCB5KSArIHF1ZXJ5KG1pZCArIDEsIHIsIGlkIDw8IDEgfCAxLCB4LCB5KTsKfQoKbWFwIDwgaW50LCBzZXQgPCBpbnQgPiA+IE07CgppbnQgbWFpbigpIHsKCWludCBuOwoJc2NhbmYoIiVkIiwgJm4pOwoJZm9yKGludCBpID0gMTsgaSA8PSBuOyArK2kpIHsKCQlzY2FuZigiJWQiLCBBICsgaSk7CgoJCU1bQVtpXV0uaW5zZXJ0KDApOwoJCQoJCWF1dG8gaXQgPSBNW0FbaV1dLmVuZCgpOwoJCS0taXQ7CgkJTGVmdFtpXSA9ICppdDsKCgkJTVtBW2ldXS5pbnNlcnQoaSk7Cgl9Cglmb3IoaW50IGkgPSAxOyBpIDw9IG47ICsraSkgewoJCXVwZGF0ZSgxLCBuLCAxLCBpLCAwLCBBW2ldLCAtMSwgTGVmdFtpXSk7Cgl9CgoJaW50IHE7CglzY2FuZigiJWQiLCAmcSk7Cglmb3IoaW50IGkgPSAxOyBpIDw9IHE7ICsraSkgewoJCWNoYXIgYzsKCQlpbnQgeCwgeTsKCQlzY2FuZigiICVjICVkICVkIiwgJmMsICZ4LCAmeSk7CgkJaWYoYyA9PSAnUScpIHsKCQkJaW50IGFucyA9IHF1ZXJ5KDEsIG4sIDEsIHgsIHkpOwoJCQlwcmludGYoIiVkXG4iLCBhbnMpOwoJCX0KCQllbHNlIGlmKEFbeF0gIT0geSkgewoKCQkJTVt5XS5pbnNlcnQoMCk7CgkJCWF1dG8gaXQgPSBNW3ldLmxvd2VyX2JvdW5kKHgpOwoJCQlhdXRvIGl0MyA9IE1bQVt4XV0udXBwZXJfYm91bmQoeCk7CgkJCWF1dG8gaXQyID0gaXQ7CgkJCS0taXQ7CgkJCXVwZGF0ZSgxLCBuLCAxLCB4LCBBW3hdLCB5LCBMZWZ0W3hdLCAqaXQpOwoJCQlpZihpdDIgIT0gTVt5XS5lbmQoKSkgewoJCQkJdXBkYXRlKDEsIG4sIDEsICppdDIsIHksIHksIExlZnRbKml0Ml0sIHgpOwoJCQkJTGVmdFsqaXQyXSA9IHg7CgkJCX0gCgkJCWlmKGl0MyAhPSBNW0FbeF1dLmVuZCgpKSB7CgkJCQl1cGRhdGUoMSwgbiwgMSwgKml0MywgQVt4XSwgQVt4XSwgeCwgTGVmdFt4XSk7CgkJCQlMZWZ0WyppdDNdID0gTGVmdFt4XTsKCQkJfQoJCQlNW3ldLmluc2VydCh4KTsKCQkJTVtBW3hdXS5lcmFzZSh4KTsKCQkJQVt4XSA9IHk7CgkJCUxlZnRbeF0gPSAqaXQ7CgoJCX0KCX0KCn0g