#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-')
			f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-48;
		ch=getchar();
	}
	return x*f;
}
int n=read(),q,len,id[1000005],a[1000005],sum[1000005],st[1000005],ed[1000005];
bool vis[1000005];
void update(int lt,int rt){
	if(id[lt]==id[rt]){
		if(vis[id[lt]]==true)
			return ;
		for(int i=lt; i<=rt; i++)
			a[i]=sqrt(a[i]);
		for(int i=st[id[lt]]; i<=ed[id[lt]]; i++){
			sum[id[lt]]-=a[i];
			a[i]=sqrt(a[i]);
			sum[id[lt]]+=a[i];
		}
		if(sum[id[lt]]==ed[id[lt]]-st[id[lt]]+1)
			vis[id[lt]]=true;
	}
	int tmp=0;
	bool f=true;
	for(int i=lt; i<=ed[id[lt]]; i++){
		sum[id[i]]-=a[i];
		a[i]=sqrt(a[i]);
		sum[id[i]]+=a[i];
	}
	if(sum[id[lt]]==ed[id[lt]]-st[id[lt]]+1)
		vis[id[lt]]=true;
	for(int i=id[lt]+1; i<id[rt]; i++){
		if(vis[i]==true)
			continue;
		for(int j=st[i]; j<=ed[i]; j++){
			sum[i]-=a[j];
			a[j]=sqrt(a[j]);
			sum[i]+=a[j];
		}
		if(sum[i]==ed[i]-st[i]+1)
			vis[i]=true;
	}
	for(int i=st[id[rt]]; i<=rt; i++){
		sum[id[i]]-=a[i];
		a[i]=sqrt(a[i]);
		sum[id[i]]+=a[i];
	}
	if(sum[id[rt]]==ed[id[rt]]-st[id[rt]]+1)
		vis[id[rt]]=true;
	return;
}
int query(int lt,int rt){
	if(id[lt]==id[rt]){
		int tmp=0;
		for(int i=lt; i<=rt; i++)
			tmp+=a[i];
		return tmp;
	}
	int tmp=0;
	for(int i=lt; i<=ed[id[lt]]; i++)
		tmp+=a[i];
	for(int i=id[lt]+1; i<id[rt]; i++)
		tmp+=sum[i];
	for(int i=st[id[rt]]; i<=rt; i++)
		tmp+=a[i];
	return tmp;
}
signed main(){
//	freopen("luogu4145.out","w",stdout);
	len=sqrt(n);
	for(int i=1; i<=n; i++){
		a[i]=read();
		id[i]=(i-1)/len+1;
		sum[id[i]]+=a[i];
	}
	for(int i=1; i<=id[n]; i++){
		st[i]=(i-1)*len+1;
		ed[i]=min(i*len,n);
		if(sum[i]==ed[i]-st[i]+1)
			vis[i]=true;
	}
	q=read();
	while(q--){
		int op=read();
		if(op==0){
			int lt=read(),rt=read(); 
			update(lt,rt);
		}
		else{
			int lt=read(),rt=read();
			cout<<query(lt,rt)<<endl;
		}
	}
	return 0;
}