#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 = 0; int join(int l, int r) { return l + r; } int ljoin(int l, int r) { return 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) { return query(0, a.size() - 1, 1, l, r); } void update(int l, int r, int val) { 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; bool sub2 = 1, sub3 = 1; for (auto x : a) if (x > 2) sub2 = 0; set<int> p2; segtree s(n, a), s2(n, a); int l1 = n - 1; for (int i = 0; i < n; ++i) if (a[i] == 2) p2.insert(i); for (int j = n - 1; j >= 0; --j) if (a[j] == 2) p2.erase(j), l1 = j - 1; else break; 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] }); int q, upd = 0; cin >> q; for(int qi = 0; qi < q; ++qi) { int t; cin >> t; if (t == 1) { if (sub2) { if (!p2.size()) continue; int idx = *p2.rbegin(); p2.erase(*p2.rbegin()); s.update(idx, idx, 1); s.update(l1, l1, 2); --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.redo(n, a); } ++upd; } else { int l, r; cin >> l >> r; --l, --r; if (sub2) cout << s.query(l, r) << 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; }