#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";
}
