#include<cstdio>
#include<cmath>
#include<cassert>
#include<algorithm>

#define lowbit(x) x&(-x)

using namespace std;

typedef long long ll;

const int maxn=100000+10;
const int tlim=7;

const bool on_luogu=true;

ll tree[maxn]={};
int t[maxn]={};
int nxt[maxn]={};

int n=0,m=0;
ll ind=0;

inline int find(int x)
{
	if(nxt[x]==x) return x;
	return nxt[x]=find(nxt[x]);
}

inline void update(int x,ll v)
{
	++t[x];
	while(x<=n)
	{
		tree[x]+=v;
		x+=lowbit(x);
	}
}

inline ll query(int x)
{
	ll sum=0;
	while(x)
	{
		sum+=tree[x];
		x-=lowbit(x);
	}
	return sum;
}

int main(void)
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&ind);
		update(i,ind);
		nxt[i]=i;
	}
	scanf("%d",&m);
	int op,a,b;
	while(m--)
	{
		scanf("%d%d%d",&op,&a,&b);
		if(on_luogu) ++op;
		if(a>b) swap(a,b);
		if(op==1)
		{
			int i=a;
			while(i<=b)
			{
				while(i!=nxt[i]) i=nxt[i];
				if(t[i]==tlim) 
				{	
					int j=i+1;
					while(j<n)
					{ 
						if(nxt[j]!=j) j=nxt[j];
						if(nxt[j]==j) {nxt[i]=j;break;}
						if(j>=n) nxt[i]=n;
					} 
				}
				if(i>b) break; 
				ll x=query(i)-query(i-1);
				update(i,floor(sqrt(x))-x);
				i++;
			} 
			/*
			printf("////////////////////\n");
			for(int i=1;i<n;i++) printf("%lld ",query(i)-query(i-1));
			printf("\n////////////////////\n");
			*/
		}
		else
			printf("%lld\n",query(b)-query(a-1));
	}
	return 0;
}