#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define int long long
const int maxn = 200005;
const int maxm = 505;
const int maxs = 2005;
const int mod = 1e9 + 7;
const int inf = 1e17;
using namespace std;
#if 0
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
#endif
#if 0
class DSU {
public:
vector<int> p, rank;
DSU(int n) {
p.resize(n), rank.resize(n, 1);
for (int i = 0; i < n; ++i) p[i] = i;
}
int fset(int x) { return p[x] = ((p[x] == x) ? x : fset(p[x])); }
bool iset(int x, int y) { return fset(x) == fset(y); }
void uset(int x, int y) {
x = fset(x), y = fset(y);
if (x == y) return;
if (rank[x] > rank[y]) swap(x, y);
p[x] = y, rank[y] += rank[x];
}
};
#endif
#if 1
class segtree {
private:
vector<int> st, lazy, a;
const int dv = 0;
const int ldv = -1;
int join(int l, int r) {
return l + r;
}
int ljoin(int l, int r) {
return (r == -1? l : r);
}
void upd(int s, int e, int node, int val) {
if (val == ldv) return;
st[node] = ((e - s + 1) * val);
}
int build(int s, int e, int node) {
if (s == e)
return st[node] = a[s];
int mid = (s + e) / 2;
return st[node] = join(build(s, mid, node * 2), build(mid + 1, e, node * 2 + 1));
}
void update(int s, int e, int node, int l, int r, int val) {
if ((l > e) || (r < s)) return;
if ((l <= s) && (r >= e)) {
upd(s, e, node, val);
lazy[node] = ljoin(lazy[node], val);
return;
}
int mid = (s + e) / 2;
upd(s, mid, node * 2, lazy[node]);
upd(mid + 1, e, node * 2 + 1, lazy[node]);
lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
lazy[node] = ldv;
update(s, mid, node * 2, l, r, val);
update(mid + 1, e, node * 2 + 1, l, r, val);
st[node] = join(st[node * 2], st[node * 2 + 1]);
}
int query(int s, int e, int node, int l, int r) {
if ((l > e) || (r < s)) return dv;
if ((l <= s) && (r >= e)) return st[node];
int mid = (s + e) / 2;
upd(s, mid, node * 2, lazy[node]);
upd(mid + 1, e, node * 2 + 1, lazy[node]);
lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
lazy[node] = ldv;
return join(query(s, mid, node * 2, l, r),
query(mid + 1, e, node * 2 + 1, l, r));
}
public:
segtree(int n, vector<int> arr) {
a = arr;
st.resize(4 * n, dv);
lazy.resize(4 * n, ldv);
build(0, n - 1, 1);
}
void redo(int n, vector<int> arr) {
a = arr;
st.resize(4 * n, dv);
lazy.resize(4 * n, ldv);
build(0, n - 1, 1);
}
int query(int l, int r) {
if (l > r) return 0;
return query(0, a.size() - 1, 1, l, r);
}
void update(int l, int r, int val) {
if(l > r) return;
update(0, a.size() - 1, 1, l, r, val);
}
};
#endif
#if 0
int p[200005][20], dep[200005];
vector<int> g[200005];
void dfs(int node, int par) {
p[node][0] = par;
dep[node] = dep[par] + 1;
for (int i = 1; i < 20; ++i)
p[node][i] = p[p[node][i - 1]][i - 1];
for (auto x : g[node])
if (x != par) dfs(x, node);
}
int kpar(int node, int k) {
for (int i = 0; i < 20; ++i)
if (k & (1 << i))
node = p[node][i];
return node;
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
u = kpar(u, dep[u] - dep[v]);
if (u == v) return u;
for (int i = 19; i >= 0; --i)
if (p[u][i] != p[v][i])
u = p[u][i],
v = p[v][i];
return p[u][0];
}
#endif
#if 0
class line {
public:
int m, c;
line(int a = 0, int b = 0) { m = a, c = b; }
int y(int x) { return m * x + c; }
};
class CHT {
private:
int i = 0;
vector<line> arr;
bool bad(line a, line b, line c) {
if (b.m == c.m) return b.c >= c.c;
double x = (c.c - a.c) / (a.m - c.m);
double y = (b.c - a.c) / (a.m - b.m);
return ((y - x) > (double)(1e-6));
}
public:
void add(int m, int c) {
line l(m, c);
if (arr.size() < 2) {
if (arr.size() == 1)
if (arr.back().m == m)
if (arr.back().c >= c)
arr.pop_back();
arr.push_back(l);
return;
}
while (arr.size() > 1) {
line pprev = arr[arr.size() - 2], prev = arr.back();
if (!bad(pprev, prev, l)) break;
arr.pop_back();
}
arr.push_back(l);
}
int query(int x) {
if (arr.empty()) return inf;
if (i >= arr.size()) i = arr.size() - 1;
while (i < (arr.size() - 1)) {
int cur = arr[i].y(x);
int nxt = arr[i + 1].y(x);
if (nxt > cur) break;
++i;
}
return arr[i].y(x);
}
};
#endif
void solve() {
int n; cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;
int q, upd = 0; cin >> q;
bool sub2 = 1, sub3 = 1;
for (auto x : a) if (x > 2) sub2 = 0;
vector<int> p2, a2(n+q, 0);
int l1 = n - 1;
for (int i = 0; i < n; ++i)
if (a[i] == 2) p2.push_back(i), a2[i] = 1;
else l1 = i;
vector<pair<int, int>> dec;
int mn = inf;
for (int i = 0; i < n; ++i)
if (a[i] < mn)
mn = a[i], dec.push_back({ i, a[i] });
segtree s(n+q, a2), s2(n, a);
for (int qi = 0; qi < q; ++qi) {
int t; cin >> t;
if (t == 1) {
if (sub2) {if(upd < (p2.size() - 1)) --l1;}
else if (upd <= 10) {
for (int i = 0; i < (n - 1); ++i)
if (a[i] > a[i + 1])
swap(a[i], a[i + 1]), s2.update(i, i, a[i]), s2.update(i + 1, i + 1, a[i + 1]);
}
++upd;
}
else {
int l, r; cin >> l >> r; --l, --r;
if (sub2) {
if (upd == 0) cout << s.query(l, r) + r - l + 1 << endl;
else if (upd >= p2.size()) cout << (r - l + 1) + max(0ll, r - l1) << endl;
else {
int idx = p2[upd - 1];
s.update(0, idx, 0), s.update(n, n + upd - 1, 1);
int res = s.query(l + upd, r + upd);
cout << res + r - l + 1 << endl;
}
}
else if (r == 0) {
auto best = *prev(lower_bound(dec.begin(), dec.end(), make_pair(upd, inf)));
cout << best.second << endl;
}
else
cout << s2.query(l, r) << endl;
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
