rt

#include <bits/stdc++.h>
#define op return
#define AK 0
#define IOI ;
#define ll long long
#define ld long double
#define ull unsigned ll
#define lll __int128
#define pii pair<int,int>
#define pip pair<int,pii>
#define ppp pair<pii,pii>
#define deb cerr<<"op AK IOI\n"
#define tostring(a) #a
#define cono(a,b) a##b
#define psa(i) (i=-~(i))
#define range(i) (-~(i))
#define mid (l+r>>1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

inline ll read()
{
	ll s=0;int w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^'0'),ch=getchar();
	return s*w;
}
void IO()
{
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
const int N=1e5+10;int n,len;
ll block[N],maxx[N],a[N],pos[N],idx[N];
void build()
{
	len=sqrt(n);
	for(int i=1;i<=n;psa(i))
	{
		idx[i]=(i-1)/len+1;
		block[idx[i]]+=a[i];
		if(a[i]>maxx[idx[i]])maxx[idx[i]]=a[i],pos[idx[i]]=i;
	}
}
ll query(int l,int r)
{
	r=min(r,n);ll ans=0;
	int p1=idx[l],p2=idx[r];
	if(p1==p2){for(;l<=r;psa(l))ans+=a[l];return ans;}
	for(;l<=p1*len;psa(l))ans+=a[l];
	for(int i=(p2-1)*len+1;i<=r;psa(i))ans+=a[i];
	for(psa(p1);p1!=p2;psa(p1))ans+=block[p1];
	return ans;
}
void update(int l,int r)
{
	r=min(r,n);
	int p1=idx[l],p2=idx[r];
	if(p1==p2)
	{
		if(maxx[p1]==1)return;
		for(int i=l;i<=r;psa(i))
		{
			ll tmp=a[i];
			a[i]=sqrt(a[i]);
			block[p1]-=(tmp-a[i]);
		}
		if(pos[p1]>=l&&pos[p1]<=r)
		{
			maxx[p1]=0;int rlim=min(n,p1*len);
			for(int i=(p1-1)*len+1;i<=rlim;psa(i))
				if(maxx[p1]<a[i])maxx[p1]=a[i],pos[p1]=i;
		}return;
	}
	if(maxx[p1]!=1)
	{
		for(int i=l;i<=p1*len;psa(i))
		{
			ll tmp=a[i];
			a[i]=sqrt(a[i]);
			block[p1]-=(tmp-a[i]);
		}
		if(pos[p1]>=l&&pos[p1]<=p1*len)
		{
			maxx[p1]=0;
			for(int i=(p1-1)*len+1;i<=p1*len;psa(i))
				if(maxx[p1]<a[i])maxx[p1]=a[i],pos[p1]=i;
		}
	}
	if(maxx[p2]!=1)
	{
		for(int i=(p2-1)*len+1;i<=r;psa(i))
		{
			ll tmp=a[i];
			a[i]=sqrt(a[i]);
			block[p2]-=(tmp-a[i]);
		}
		if(pos[p2]>=(p2-1)*len&&pos[p2]<=r)
		{
			maxx[p2]=0;int rlim=min(n,p2*len);
			for(int i=(p2-1)*len+1;i<=rlim;psa(i))
				if(maxx[p2]<a[i])maxx[p2]=a[i],pos[p2]=i;
		}
	}
	for(psa(p1);p1!=p2;psa(p1))
	{
		maxx[p1]=sqrt(maxx[p1]);
		if(maxx[p1]==1){block[p1]=len;continue;}
		for(int i=(p1-1)*len+1;i<=p1*len;psa(i))
		{
			ll tmp=a[i];
			a[i]=sqrt(a[i]);
			block[p1]-=(tmp-a[i]);
		}
	}
}
signed main()
{
	n=read();
	for(int i=1;i<=n;psa(i))a[i]=read();
	build();int q=read(),opt,l,r;
	while(q--)
	{
		opt=read(),l=read(),r=read();
		if(l>r)swap(l,r);
		if(opt)printf("%lld\n",query(l,r));
		else update(l,r);
//		for(int i=1;i<=idx[n];psa(i))printf("%d\n",block[i]);
	}
	op AK IOI
}

@YaeMiko_ @mashduihca @syta @operator_ @sjbbszgyd @Qian_xscc @OcTar @h_rains @Yokki @dogjuan @waauto