#include<iostream> #include<vector> #include<algorithm> #define int long long const int maxn = 500005; const int inf = 1e17; using namespace std; //W segtree struct segtree { int t[2 * maxn], n; void build() { for (int i = n - 1; i > 0; --i) t[i] = t[i << 1] + t[i << 1 | 1]; } void update(int p, int value) { for (t[p += n] = value; p > 1; p >>= 1) t[p >> 1] = t[p] + t[p ^ 1]; } int query(int l, int r) { int res = 0; for (l += n, r += (n + 1); l < r; l >>= 1, r >>= 1) { if (l & 1) res += t[l++]; if (r & 1) res += t[--r]; } return res; } void init(int N, vector<int> a) { for (int i = 0; i < N; ++i) t[i + N] = a[i]; n = N, build(); } }; ///////////////////////////////////////////////////////////////// vector<int> a, res, idx; vector<pair<int, int>> arr; vector<pair<int, pair<int, int>>> qs; segtree s1, s2; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; a.resize(n), idx.resize(n), arr.resize(n); for (auto& x : a) cin >> x; for (int i = 0; i < n; ++i) arr[i] = { a[i], i }; sort(arr.begin(), arr.end()); for (int i = 0; i < n; ++i) idx[arr[i].second] = i; s1.init(n, vector<int>(n, 0)); s2.init(n, vector<int>(n, 0)); int q, k = 0; cin >> q; while (q--) { int t; cin >> t; if (t == 1) ++k; else { int l, r; cin >> l >> r; l -= 2, --r; if (l >= 0) qs.push_back({ l + k + 1, {l + 1, -(int)res.size() - 1} }); qs.push_back({ r + k + 1, {r + 1, res.size() + 1 } }); res.push_back(0); } } sort(qs.begin(), qs.end()); int j = 0; for (int i = 0; i < qs.size(); ++i) { while ((j < n) && (j < qs[i].first)) s1.update(idx[j], a[j]), s2.update(idx[j], 1), ++j; int s = 0, e = n - 1, ksm = n - 1; while (s <= e) { int m = (s + e) / 2; if (s2.query(0, m) >= qs[i].second.first) ksm = m, e = m - 1; else s = m + 1; } int ans = s1.query(0, ksm); int l = qs[i].second.second; res[abs(l) - 1] += (l / abs(l)) * ans; } for (auto x : res) cout << x << endl; }