#include<iostream>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
#define endl '\n'
const int N=5e5+7;
int tre[4*N],lazy[4*N],arr[N],n,q,tag,x,y,ans;
int ln[4*N],rn[4*N];

inline void olazy(int node){
    if(!lazy[node]) return;
    lazy[2*node]+=lazy[node];
    lazy[2*node+1]+=lazy[node];
    lazy[node]=0;
    return;
}

void build(int l,int r,int node){
    int mid=(l+r)>>1;
    ln[node]=l;
    rn[node]=r;
    tre[node]=arr[r]-arr[l-1];
    if(l!=r) build(l,mid,2*node);
    if(l!=r) build(mid+1,r,2*node+1);
    return;
}

void fid(int l,int r,int node){
    if(tre[node]==(rn[node]-ln[node]+1)) return;
    if(ln[node]>=l&&rn[node]<=r){
        lazy[node]+=1;
        return;
    }
    if(ln[2*node]<=r&&rn[2*node]>=l) fid(l,r,2*node);
    if(ln[2*node+1]<=r&&rn[2*node+1]>=l) fid(l,r,2*node+1);
    return;
}

int trueans(int node){
    if(tre[node]==(rn[node]-ln[node]+1)) return tre[node];
    if(ln[node]==rn[node]){
        for(int i=1;i<=lazy[node];i++){
            if(tre[node]<=1) break;
            tre[node]=sqrt(tre[node]);
        }
        olazy(node);
        return tre[node];
    }
    olazy(node);
    trueans(2*node);
    trueans(2*node+1);
    tre[node]=tre[2*node]+tre[2*node+1];
    return tre[node];
}

void fidans(int node){
    if(ln[node]>=x&&rn[node]<=y){
        ans+=trueans(node);
        return;
    } 
    olazy(node);
    if(ln[2*node]<=y&&rn[2*node]>=x) fidans(2*node);
    if(ln[2*node+1]<=y&&rn[2*node+1]>=x) fidans(2*node+1);
    return;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        arr[i]+=arr[i-1];
    }
    build(1,n,1);
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>tag>>x>>y;
        if(x>y) swap(x,y);
        if(tag==0) fid(x,y,1);
        else {
            ans=0;
            fidans(1);
            cout<<ans<<endl;
        }
    }
    return 0;
}

hack点T了，求解，玄关！