#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define N 2000009
#define int long long
using namespace std;
int n,m,a[N],sq_cnt,sq_len,bef[N],now=1,bel[N];
struct Node{
    int from,to,sum,zero;
}sq[N];
int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
void init(){
    for(int i=1;i<=n;i+=sq_len){
        sq[++sq_cnt].from=i;
        sq[sq_cnt].to=min(i+sq_len-1,n);
    }
}
void get_num(){
    for(int i=1;i<=sq_cnt;i++){
        sq[i].sum=bef[sq[i].to]-bef[sq[i].from-1];
        sq[i].zero=0;
    }
}
void modify(int l,int r){
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            sq[bel[i]].sum-=a[i];
            a[i]=sqrt(a[i]);
            sq[bel[i]].sum+=a[i];
        }
        return ;
    }
    for(int i=l;i<=sq[bel[l]].to;i++){
        sq[bel[i]].sum-=a[i];
        a[i]=sqrt(a[i]);
        sq[bel[i]].sum+=a[i];
    }
    for(int i=sq[bel[r]].from;i<=r;i++){
        sq[bel[i]].sum-=a[i];
        a[i]=sqrt(a[i]);
        sq[bel[i]].sum+=a[i];
    }
    for(int j=bel[l]+1;j<bel[r];j++){
        if(sq[j].zero){
            continue;
        }
        for(int i=sq[j].from;i<=sq[j].to;i++){
            sq[bel[i]].sum-=a[i];
            a[i]=sqrt(a[i]);
            sq[bel[i]].sum+=a[i];
        }
        if(sq[j].sum<=sq[j].to-sq[j].from+1){
            sq[j].zero=0;
        }
    }
}
int query(int l,int r){
    int ans=0;
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            ans+=a[i];
        }
        return ans;
    }
    for(int i=l;i<=sq[bel[l]].to;i++){
        ans+=a[i];
    }
    for(int i=sq[bel[r]].from;i<=r;i++){
        ans+=a[i];
    }
    for(int i=bel[l]+1;i<bel[r];i++){
        ans+=sq[i].sum;
    }
    return ans;
}
signed main(){
    cin>>n;
    sq_len=sqrt(n);
    init();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(i>sq[now].to){
            now++;
        }
        bel[i]=now;
        bef[i]=bef[i-1]+a[i];
    }
    get_num();
    cin>>m;
    for(int i=1;i<=m;i++){
        int q,x,y;
        q=read(),x=read(),y=read();
        if(x>y){
            swap(x,y);
        }
        if(q==0){
            modify(x,y);
        }
        else cout<<query(x,y)<<endl;
    }
    return 0;
}