#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;
}