#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;
#define all(x) (x).begin(), (x).end()
#define fap(x) cerr << __LINE__ << " says: " << #x << " = " << x << "\n"
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int inf = 0x3f3f3f3f;
const ll INF = 2e18;

/*
        Order Statistics Tree ( OST )

        find_by_order()
                takes an integer k and returns an iterator to the k'th largest element counting from zero
        order_of_key()
                takes an element, here an integer and returns the number of elements strictly smaller than input
*/

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int N = 2e5 + 7;

namespace SQ {
	const int BLOCK = 450;
	list<pii> seq[BLOCK];
	int active[BLOCK];

	void init() {
		for(int i=0; i<BLOCK; ++i) {
			active[i] = 0;
			seq[i].clear();
		}
		active[0] = 1;
		seq[0].push_back(pii(1, inf));
	}

	void insert(int pos, int id) {
		int which = -1;
		for(int i=0; i<BLOCK; ++i) {
			if(active[i] >= pos) {
				which = i;
				break;
			}
			pos -= active[i];
		}

		assert(which > -1);
		for(auto it = seq[which].begin(); it != seq[which].end(); ++it) {
			pos -= it->first;
			if(pos <= 0) {
				seq[which].insert(it, pii(1, id));
				++active[which];
				break;
			}
		}

		for(int i=which; i+1 < BLOCK and (int) seq[i].size() > BLOCK; ++i) {
			pii qq = seq[i].back();
			seq[i].pop_back();
			active[i] -= qq.first;
			seq[i+1].push_front(qq);
			active[i+1] += qq.first;
		}
	}

	void erase(int pos) {
		int which = -1;
		for(int i=0; i<BLOCK; ++i) {
			if(active[i] >= pos) {
				which = i;
				break;
			}
			pos -= active[i];
		}

		assert(which > -1);
		for(auto it = seq[which].begin(); it != seq[which].end(); ++it) {
			pos -= it->first;
			if(pos <= 0 and it->first) {
				it->first = 0;
				--active[which];
				break;
			}
		}
	}

	vector<int> get_seq() {
		vector<int> ret;
		for(int i=0; i<BLOCK; ++i) {
			if(seq[i].empty()) break;
			for(auto qq : seq[i]) {
				ret.push_back(qq.second);
			}
		}
		if(!ret.empty() and ret.back() == inf) ret.pop_back();
		return ret;
	}

	void prnt() {
		for(int i=0; i<BLOCK; ++i) {
			if(seq[i].empty()) break;
			if(!active[i]) continue;
			for(auto qq : seq[i]) {
				if(qq.first and qq.second < inf) cout << qq.second << " ";
			}
		}
		cout << " -- |\n";
	}
};

namespace SegTree {
	struct dat {
		int sum, lsum, rsum, best;
		int negcnt, max_neg;

		dat(int val = 0) {
			sum = lsum = rsum = best = val;
			negcnt = (val < 0);
			max_neg = (val < 0 ? val : -inf);
		}
		dat operator + (const dat &p) {
			dat ret;
			ret.sum = sum + p.sum;
			ret.lsum = max(lsum, sum + p.lsum);
			ret.rsum = max(rsum + p.sum, p.rsum);
			ret.best = max(max(best, p.best), rsum + p.lsum);
			ret.negcnt = negcnt + p.negcnt;
			ret.max_neg = max(max_neg, p.max_neg);
			return ret;
		}
	} tr[4*N];

	void update(int at, int l, int r, int pos, int val) {
		if(l == r) {
			tr[at] = dat(val);
			// cerr << l << " " << r << ": " << tr[at].best << " " << tr[at].lsum << " " << tr[at].rsum << " " << tr[at].sum << "\n";
			return ;
		}

		int lc = (at << 1), rc = ((at << 1) ^ 1), mid = ((l + r) >> 1);
		if(pos <= mid) update(lc, l, mid, pos, val);
		else update(rc, mid + 1, r, pos, val);

		tr[at] = tr[lc] + tr[rc];
		// cerr << l << " " << r << ": " << tr[at].best << " " << tr[at].lsum << " " << tr[at].rsum << " " << tr[at].sum << "\n";
	}

	dat query(int at, int l, int r, int lo, int hi) {
		if(l > hi or r < lo) return dat(0);
		if(l >= lo and r <= hi) return tr[at];

		int lc = (at << 1), rc = ((at << 1) ^ 1), mid = ((l + r) >> 1);
		dat q1 = query(lc, l, mid, lo, hi);
		dat q2 = query(rc, mid + 1, r, lo, hi);
		return q1 + q2;
	}
};

struct Query {
	char op;
	int x, y;
} qu[N];

int a[N];
int aidx[N], qidx[N];	// array and query element position in new arr

void precal(int n, int q) {
	SQ::init();

	for(int i=1; i<=n; ++i) SQ::insert(i, i);
	for(int i=1; i<=q; ++i) {
		if(qu[i].op == 'I') SQ::insert(qu[i].x, -i);
		else if(qu[i].op == 'D') SQ::erase(qu[i].x);
	}

	vector<int> v = SQ::get_seq();
	for(int i=0; i<(int) v.size(); ++i) {
		if(v[i] > 0) aidx[v[i]] = i + 1;
		else qidx[-v[i]] = i + 1;
	}
}

void prnt(ordered_set &ost) {
	for(auto qq : ost) cerr << qq << " ";
	cerr << " -- - OST\n";
}

int main() {
	FastIO;

	int n;
	cin >> n;
	for(int i=1; i<=n; ++i) cin >> a[i];

	int q;
	cin >> q;
	for(int i=1; i<=q; ++i) {
		cin >> qu[i].op >> qu[i].x;
		if(qu[i].op != 'D') cin >> qu[i].y;
		if(qu[i].op == 'Q' and qu[i].x > qu[i].y) swap(qu[i].x, qu[i].y);
	}

	precal(n, q);

	int nn = n + q;
	ordered_set ost;
	for(int i=1; i<=n; ++i) {
		ost.insert(aidx[i]);
		SegTree::update(1, 1, nn, aidx[i], a[i]);

	}
	// prnt(ost);

	for(int i=1; i<=q; ++i) {
		if(qu[i].op == 'I') {
			ost.insert(qidx[i]);
			SegTree::update(1, 1, nn, qidx[i], qu[i].y);
		}
		else if(qu[i].op == 'D') {
			auto it = ost.find_by_order(qu[i].x - 1);
			assert(it != ost.end());
			SegTree::update(1, 1, nn, *it, 0);
			ost.erase(it);
		}
		else if(qu[i].op == 'R') {
			auto it = ost.find_by_order(qu[i].x - 1);
			assert(it != ost.end());
			SegTree::update(1, 1, nn, *it, qu[i].y);
		}
		else {
			auto lit = ost.find_by_order(qu[i].x - 1);
			auto rit = ost.find_by_order(qu[i].y - 1);
			assert(lit != ost.end() and rit != ost.end());

			auto temp = SegTree::query(1, 1, nn, *lit, *rit);
			int len = qu[i].y - qu[i].x + 1;
			int res;
			if(temp.negcnt == len) res = temp.max_neg;
			else res = temp.best;
			cout << res << "\n";
		}
		// prnt(ost);
	}

	return 0;
}