#include<bits/stdc++.h>
#define int long long
using namespace std;
int jz[900001][21];//开跟树枝
int sum[900001][21];//到第i数级别为j前缀和
//称1个数相交最初开了几次跟成为他的级别
struct Tree {
	int l,r;
	int lazy;//将所有数的级别加1
	int SUM;
	int lvl;
} tree[900001];
int n,m;
int a[900001];
int ans;
void buildtree(int p,int l,int r) {
	tree[p].l=l;
	tree[p].r=r;
	tree[p].SUM=sum[r][0]-sum[l-1][0];
	if(l==r)return ;
	int mid=(l+r)>>1;
	buildtree(p*2,l,mid);
	buildtree(p*2+1,mid+1,r);
}
void pushdown(int p) {
	if(tree[p*2].lvl>6){}
    else{
        tree[p*2].SUM=sum[tree[p*2].r][tree[p*2].lvl+tree[p].lazy]-sum[tree[p*2].l-1][tree[p*2].lvl+tree[p].lazy];
	tree[p*2].lvl+=tree[p].lazy;
	tree[p*2].lazy+=tree[p].lazy;
    }
	if(tree[p*2+1].lvl>6){}
    else{
        tree[p*2+1].SUM=sum[tree[p*2+1].r][tree[p*2+1].lvl+tree[p].lazy]-sum[tree[p*2+1].l-1][tree[p*2+1].lvl+tree[p].lazy];
	tree[p*2+1].lvl+=tree[p].lazy;
	tree[p*2+1].lazy+=tree[p].lazy;
    }
	tree[p].lazy=0;
}
void pushup(int p) {
	tree[p].SUM=tree[p*2].SUM+tree[p*2+1].SUM;
}
void sqrt916(int p,int x,int y) {
	pushdown(p);
	int l=tree[p].l,r=tree[p].r;
	if(l>=x&&r<=y) {
		tree[p].lazy+=1;//study times plus plus
		if(tree[p].lvl>15)tree[p].lvl--;
		tree[p].SUM=sum[r][tree[p].lvl+1]-sum[l-1][tree[p].lvl+1];
		tree[p].lvl++;
		return ;
	}
	pushdown(p);
	int mid=l+r>>1;
	if(mid>=x)sqrt916(p*2,x,y);
	if(mid+1<=y)sqrt916(p*2+1,x,y);
	pushup(p);
	return ;
}
void ques916(int p,int x,int y) {
	pushdown(p);
	int l=tree[p].l,r=tree[p].r;
	if(l>=x&&r<=y) {
		ans+=tree[p].SUM;
		return ;
	}
	int mid=l+r>>1;
	if(mid>=x)ques916(p*2,x,y);
	if(mid+1<=y)ques916(p*2+1,x,y);
	pushup(p);
	return ;
}
signed main() {
	cin>>n;
	for(int i=1; i<=n; i++)cin>>a[i];
	for(int i=1; i<=n; i++) {
		jz[i][0]=a[i];
		for(int j=1; j<=20; j++) {
			jz[i][j]=sqrt(jz[i][j-1]);
            if(!jz[i][j])jz[i][j]++;
		}
	}
	for(int j=0; j<=20; j++) {
		for(int i=1; i<=n; i++) {
			sum[i][j]=sum[i-1][j]+jz[i][j];
		}
	}
	buildtree(1,1,n);
	cin>>m;
	for(int i=1; i<=m; i++) {
		int op;
		cin>>op;
		if(op==0) {
			int x,y;
			cin>>x>>y;
            if(x>y)swap(x,y);
			sqrt916(1,x,y);
		}
		if(op==1) {
			int x,y;
			cin>>x>>y;
            if(x>y)swap(x,y);
			ans=0;
			ques916(1,x,y);
			cout<<ans<<endl;
		}
	}
	return 0;
    //let me AC
    //20loveeat progress 20598
}