#include <bits/stdc++.h>
#include <queue>
#define int long long
#define arr3 array <int , 3>
#define pii pair <int , int>
#define fi first
#define se second
#define BIT(x , k) ((x >> k)&1)
#define MASK(x) (1 << x)
using namespace std;
const int INF = 1e18;
const int maxn = 1e6 + 7;
pii st[maxn*4];
void update(int id , int l , int r , int pos , int val)
{
if(r < pos || l > pos) return;
if(l == r)
{
st[id] = {1 , val};
return;
}
int mid = (l+r)>>1;
update(id*2 , l, mid , pos , val);
update(id*2+1 , mid+1 , r , pos , val);
st[id].fi = st[id*2].fi + st[id*2+1].fi;
st[id].se = st[id*2].se + st[id*2+1].se;
}
int walk(int id , int l , int r , int sum)
{
if(sum == 0) return 0;
if(l == r) return st[id].se;
int mid = (l+r)>>1;
if(st[id*2].fi < sum)
{
return st[id*2].se + walk(id*2+1 , mid+1 , r , sum - st[id*2].fi);
}
return walk(id*2 , l , mid , sum);
}
int n , q, a[maxn] , ans[maxn] , b[maxn];
struct query {int cnt , id , par;};
vector <query> ask[maxn];
void compress()
{
vector <pii> val;
for(int i = 1; i <= n; i++) val.push_back({a[i] , i});
sort(val.begin() , val.end());
for(int i = 1; i <= n; i++) a[val[i-1].se] = i;
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++) {cin >> a[i]; b[i] = a[i];}
compress();
cin >> q;
for(int i = 1 , cnt = 0; i <= q; i++)
{
int t; cin >> t;
if(t == 1) cnt++;
else
{
int l , r; cin >> l >> r;
ask[min(n , l-1+cnt)].push_back({l-1 , i , -1});
ask[min(n , r+cnt)].push_back({r , i , 1});
}
}
for(int i = 1; i <= n; i++)
{
update(1 , 1 , n , a[i] , b[i]);
for(auto [cnt , id, par]: ask[i])
{
ans[id] += par*walk(1 , 1 , n , cnt);
}
}
for(int i = 1; i <= q; i++)
{
if(ans[i] == 0) continue;
cout << ans[i] << '\n';
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
solve();
return 0;
}
