#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;
#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif
const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;
int n, q, k = 0, a[mn], ans[mn], on[mn];
struct SegmentTree {
int st[mn << 2];
void update(int id, int l, int r, int u, int val){
if(l > u || r < u) return;
if(l == r){
st[id] += val;
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, val);
update(id << 1 | 1, mid + 1, r, u, val);
st[id] = st[id << 1] + st[id << 1 | 1];
}
int walk(int id, int l, int r, int val){
debug(st[id], l, r, val);
if(l == r) return l;
int mid = (l + r) >> 1;
if(st[id << 1] < val) return walk(id << 1 | 1, mid + 1, r, val);
return walk(id << 1, l, mid, val);
}
int get(int id, int l, int r, int u){
if(l > u) return 0;
if(r <= u) return st[id];
int mid = (l + r) >> 1;
return get(id << 1, l, mid, u) + get(id << 1 | 1, mid + 1, r, u);
}
} st_val, st_cnt;
vector <int> comp;
vector <tuple <int, int, int>> line[mn];
void solve() {
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
comp.push_back(a[i]);
}
sort(all(comp)); comp.erase(unique(all(comp)), comp.end());
cin >> q;
for(int i = 1; i <= q; i++){
int t; cin >> t;
k += (t == 1);
on[i] = (t == 2);
if(t == 2){
int l, r; cin >> l >> r;
line[min(l + k - 1, n)].push_back({i, l - 1, - 1});
line[min(r + k, n)].push_back({i, r, 1});
}
}
for(int i = 1; i <= n; i++){
int val = lower_bound(all(comp), a[i]) - comp.begin() + 1;
st_cnt.update(1, 1, n, val, 1);
st_val.update(1, 1, n, val, a[i]);
debug(val, a[i]);
for(auto [id, sz, hs] : line[i]){
int pos = st_cnt.walk(1, 1, n, sz);
int cnt = st_cnt.get(1, 1, n, pos);
int val = st_val.get(1, 1, n, pos) - (cnt - sz) * comp[pos - 1];
debug(i, id, sz, hs, pos, cnt, st_val.get(1, 1, n, pos), val);
ans[id] += hs * val;
}
}
for(int i = 1; i <= q; i++){
if(on[i]) cout << ans[i] << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
#define task "Kawabata"
if (fopen(task".INP", "r")) {
freopen(task".INP", "r", stdin);
freopen(task".OUT", "w", stdout);
}
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro
