#include<bits/stdc++.h>
#define rep(u,x,y) for(int u=x;u<=y;++u)
using namespace std;
const int N=1e6+1;
typedef long long ll;
ll a[N],sum[501],res;
int n,m,id[N],len,op,l,r,sid,eid;
int kl[501],kr[501];//左右边界
bool vis[N];//是否全1 
int main(){
//	freopen("P4145_4.in","r",stdin);
	scanf("%d",&n),len=sqrt(n);
	
	rep(i,1,n)scanf("%lld",a+i),sum[id[i]=(i-1)/len+1]+=a[i];
	rep(i,1,len+1)kl[i]=(i-1)*len+1,kr[i]=min(n,i*len);
	
	scanf("%d",&m);
	while(m--){
		scanf("%d%d%d",&op,&l,&r);if(l>r)swap(l,r);
		
		sid=id[l],eid=id[r];
		if(!op){
			if(sid==eid){
				if(vis[sid])continue;
				rep(i,l,r)sum[sid]-=a[i],a[i]=sqrt(a[i]),sum[sid]+=a[i];
				if(sum[sid]==kr[sid]-kl[sid]+1)vis[sid]=1;
			}
			else{
				rep(pos,sid+1,eid-1){
					if(vis[pos])continue;
					rep(i,max(l,kl[pos]),min(r,kr[pos]))sum[pos]-=a[i],a[i]=sqrt(a[i]),sum[pos]+=a[i];
					if(sum[pos]==kr[pos]-kl[pos]+1)vis[pos]=1;
				}
				rep(i,l,kr[sid])sum[sid]-=a[i],a[i]=sqrt(a[i]),sum[sid]+=a[i];
				rep(i,kl[eid],r)sum[eid]-=a[i],a[i]=sqrt(a[i]),sum[eid]+=a[i];
				if(sum[sid]==kr[sid]-kl[sid]+1)vis[sid]=1;
				if(sum[eid]==kr[eid]-kl[eid]+1)vis[eid]=1;
			}
		}
		
		else{
			res=0;
			if(sid==eid)rep(i,l,r)res+=a[i];
			else{
				rep(i,sid+1,eid-1)res+=sum[i];
				rep(i,l,kr[sid])res+=a[i];
				rep(i,kl[eid],r)res+=a[i];
			}
			printf("%lld\n",res);
		}
	}
	return 0;
}