#include <bits/stdc++.h>
using namespace std;
const int maxn = 250010;
const int maxq = 500010;
#define LEFT 0
#define RIGHT 1
#define pii pair<int, int>
int n, q;
int a;
map<int, int> mval; //mamp from index to value
int svals[maxn];
struct node {
node *ch[2];
int indo; //either negative index or query time thing
int we; //the random weight
node *par;
node(int ii) :
indo(ii) {
we = rand() % 1000000;
ch[0] = ch[1] = NULL;
par = NULL;
}
void setChild(int dir, node *c) {
ch[dir] = c;
// cout << this->indo << " :: " << c->indo << endl;
if (c != NULL) {
c->par = this;
}
}
int getDirection() {
if (par == NULL) return -1;
if (this == par->ch[LEFT]) return LEFT;
if (this == par->ch[RIGHT]) return RIGHT;
return -1;
}
bool isroot() {
return !par || (par->ch[LEFT] != this &&
par->ch[RIGHT] != this);
}
void rotateUp() {
int dir = getDirection();
node *p = par;
if (!p->isroot()) {
p->par->ch[p->getDirection()] = this;
}
par = p->par;
node *pMid = ch[!dir];
p->setChild(dir, pMid);
setChild(!dir, p);
}
};
node *cnodes[maxn]; //current nodes
node *root = NULL;
string tp[maxq];
int qv[maxq][2];
vector<int> inorder;
int seg[maxn*4]; //we want to store a maximum seg tree
void update(int spot, int val, int ss = 1, int se = n, int si = 0) {
if (spot > se || spot < ss || ss > se) return;
if (ss == se) {
seg[si] = val;
return;
}
int mid = (ss+se)/2;
if (spot <= mid) {
update(spot, val, ss, mid, si*2+1);
}
else update(spot, val, mid+1, se, si*2+2);
seg[si] = max(seg[si*2+1], seg[si*2+2]);
}
int query(int qs, int qe, int ss = 1, int se = n, int si = 0) {
if (qs > qe || ss > se || qs > se || qe < ss) return 0;
if (qs <= ss && se <= qe) return seg[si];
int mid = (ss+se)/2;
return max(query(qs, qe, ss, mid, si*2+1),
query(qs, qe, mid+1, se, si*2+2));
}
void buildtree(int ss = 1, int se = n, int si = 0) {
if (ss == se) {
// cout << " here " << ss << " : " << mval[0-ss] << endl;
seg[si] = mval[0-ss];
return;
}
int mid = (ss+se)/2;
buildtree(ss, mid, si*2+1);
buildtree(mid+1, se, si*2+2);
seg[si] = max(seg[si*2+1], seg[si*2+2]);
}
vector<pii> befa;
vector<pii> afta;
void dfs(node *cur) {
// cout << "at: " << cur->indo << endl;
if (cur->ch[LEFT]) {
dfs(cur->ch[LEFT]);
}
inorder.push_back(cur->indo);
if (cur->ch[RIGHT]) {
dfs(cur->ch[RIGHT]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
srand(time(NULL));
cin >> n >> a;
vector<pii> stuff;
for (int i = 1; i <= n; i++) {
cin >> svals[i];
stuff.push_back(pii(svals[i], i));
}
cin >> q;
sort(stuff.begin(), stuff.end());
reverse(stuff.begin(), stuff.end());
for (pii vp : stuff) {
int ind = vp.second;
node *cur = new node(0-ind);
cnodes[ind] = cur;
if (root == NULL) {
root = cur;
continue;
}
//insert me to be the smallest guy present
node *tmp = root;
while (tmp->ch[LEFT] != NULL) {
tmp = tmp->ch[LEFT];
}
tmp->setChild(LEFT, cur);
//now we need to rotate cur up a bunch
while (!cur->isroot() &&
cur->we > cur->par->we) {
cur->rotateUp();
}
if (cur->isroot()) {
root = cur;
}
}
//store the ten greatest values at any time
vector<int> tg;
for (int i = 0; i < 10 && i < stuff.size(); i++) {
tg.push_back(stuff[i].second);
}
for (int i = 0; i < q; i++) {
// cout << " at start of " << i << " root is: " << root->indo << endl;
cin >> tp[i];
if (tp[i] == "E") {
cin >> qv[i][0] >> qv[i][1];
int ind = qv[i][0];
int ec = qv[i][1];
for (int i = 0; i < tg.size(); i++) {
if (tg[i] == ind) {
tg.erase(tg.begin() + i);
}
}
tg.insert(tg.begin() + ec-1, ind);
node *cur = new node(i);
cnodes[ind] = cur;
if (ec == 1) {
//insert this to be the biggest value we have
node *tmp = root;
while (tmp->ch[RIGHT] != NULL) {
tmp = tmp->ch[RIGHT];
}
tmp->setChild(RIGHT, cur);
}
else {
int aft = tg[ec-2];
//want to be right below this guy
node *tmp = cnodes[aft];
// cout << "THIS: " << tmp->indo << endl;
if (tmp->ch[LEFT] == NULL) {
tmp->setChild(LEFT, cur);
}
else {
tmp = tmp->ch[LEFT];
while (tmp->ch[RIGHT] != NULL) {
tmp = tmp->ch[RIGHT];
}
tmp->setChild(RIGHT, cur);
}
}
while (!cur->isroot() &&
cur->we > cur->par->we) {
cur->rotateUp();
}
if (cur->isroot()) {
root = cur;
}
}
else {
cin >> qv[i][0];
//do not really want to do anything
}
// cout << "done with index: " << i << endl;
}
// vector<int> find;
tg.clear();
for (int i = 0; i < 10 && i < stuff.size(); i++) {
tg.push_back(stuff[i].second);
}
dfs(root);
// cout << "inorder: ";
for (int i = 0; i < inorder.size(); i++) {
int v = inorder[i];
// cout << v << " ";
mval[v] = i+1;
}
// cout << endl;
buildtree();
// cout << "START: " << query(1, n) << endl;
//now we must process the queries
for (int i = a-1; i >= 1; i--) {
if (befa.size() && befa.back().first >= mval[0-i]) {
continue;
}
befa.push_back(pii(mval[0-i], i));
}
befa.push_back(pii(10000000, 0));
for (int i = a+1; i <= n; i++) {
if (afta.size() && afta.back().first >= mval[0-i]) {
continue;
}
afta.push_back(pii(mval[0-i], i));
}
afta.push_back(pii(10000000, n+1));
for (int ii = 0; ii < q; ii++) {
if (tp[ii] == "E") {
int mv = mval[ii];
int cind = qv[ii][0];
update(cind, mv);
if (cind < a) {
//update befa
for (int i = befa.size()-1; i >= 0; i--) {
if (befa[i].second > cind) {
if (befa[i].first < mv) {
befa.insert(befa.begin() + i+1, pii(mv, cind));
}
break; //do not want to do this
}
if (befa[i].first <= mv) {
befa.erase(befa.begin() + i);
}
if (i == 0) {
befa.insert(befa.begin() + 0, pii(mv, cind));
}
}
}
if (cind > a) {
//update afta
for (int i = afta.size()-1; i >= 0; i--) {
if (afta[i].second < cind) {
if (afta[i].first < mv) {
afta.insert(afta.begin() + i+1, pii(mv, cind));
}
break; //do not want to do this
}
if (afta[i].first <= mv) {
afta.erase(afta.begin() + i);
}
if (i == 0) {
afta.insert(afta.begin() + 0, pii(mv, cind));
}
}
}
}
else {
int mq = qv[ii][0];
if (mq == a) {
cout << 0 << '\n';
}
else if (mq < a) {
int bg = query(mq, a-1);
//binary search to find first ind greater than me
int lo = 0, hi = afta.size()-1;
while (lo < hi) {
int mid = (lo + hi)/2;
if (afta[mid].first > bg) {
hi = mid;
}
else lo = mid+1;
}
// if (ii == 0) cout << " value : " << bg << endl;
// if (ii == 0) cout << lo << " : " << befa[lo].second << endl;
int res = afta[lo].second - mq - 1;
cout << res << '\n';
}
else if (mq > a) {
int bg = query(a+1, mq);
int lo = 0, hi = befa.size()-1;
while (lo < hi) {
int mid = (lo + hi)/2;
if (befa[mid].first > bg) {
hi = mid;
}
else lo = mid+1;
}
int res = mq - befa[lo].second - 1;
cout << res << '\n';
}
}
}
cout.flush();
}
