#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 5e5 + 5; int bit1[maxn], bit2[maxn], ans[maxn]; vector<array<int, 3>> at[maxn]; vector<int> compress; void add(int p, int v){ for(; p < maxn; p += p & -p) bit1[p]++, bit2[p] += v; } int get(int k){ int pos = 0, cnt = 0, sum = 0; for(int i = 19; i >= 0; i--){ if(pos + (1 << i) < compress.size() && cnt + bit1[pos + (1 << i)] <= k){ pos += (1 << i); cnt += bit1[pos]; sum += bit2[pos]; } } return sum + (k - cnt) * compress[pos]; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector<int> a(n + 1); for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) compress.push_back(a[i]); sort(compress.begin(), compress.end()); compress.erase(unique(compress.begin(), compress.end()), compress.end()); int q; cin >> q; int cnt1 = 0, id = 0; while (q--){ int type; cin >> type; if(type == 1) cnt1++; else{ int l, r; cin >> l >> r; at[min(n, l - 1 + cnt1)].push_back({l - 1, id, -1}); at[min(n, r + cnt1)].push_back({r, id, 1}); id++; } } for(int i = 1; i <= n; i++){ add(lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin() + 1, a[i]); for(auto [k, id, sign]: at[i]) ans[id] += sign * get(k); } for(int i = 0; i < id; i++) cout << ans[i] << "\n"; }