#include <bits/stdc++.h>

using namespace std;

int n, sq, a[500005], st[500005], ed[500005], block[500005], sum[500005], maxa[500005];

void change(int l, int r)
{
	int lb = block[l], rb = block[r];
	if (lb == rb)
	{
		for (int i = l ; i <= r ; i ++)
		{
			if (a[i] == maxa[lb])
			{
				maxa[lb] = sqrt(a[i]);
			}
			sum[lb] -= a[i];
			sum[lb] += sqrt(a[i]);
			a[i] = sqrt(a[i]);
		}
		for (int i = st[lb] ; i <= ed[lb] ; i ++)
		{
			maxa[lb] = max(maxa[lb], a[i]);
		}
		return ;
	}
	if (maxa[lb] > 1)
	{
		for (int i = l ; i <= ed[lb] ; i ++)
		{
			if (a[i] == maxa[lb])
			{
				maxa[lb] = sqrt(a[i]);
			}
			sum[lb] -= a[i];
			sum[lb] += sqrt(a[i]);
			a[i] = sqrt(a[i]);
		}
		for (int i = st[lb] ; i <= ed[lb] ; i ++)
		{
			maxa[lb] = max(maxa[lb], a[i]);
		}
	}
	if (maxa[rb] > 1)
	{
		for (int i = st[rb] ; i <= r ; i ++)
		{
			if (a[i] == maxa[rb])
			{
				maxa[rb] = sqrt(a[i]);
			}
			sum[rb] -= a[i];
			sum[rb] += sqrt(a[i]);
			a[i] = sqrt(a[i]);
		}
		for (int i = st[rb] ; i <= ed[rb] ; i ++)
		{
			maxa[rb] = max(maxa[rb], a[i]);
		}
	}
	for (int i = lb + 1 ; i <= rb - 1 ; i ++)
	{
		if (maxa[i] > 1)
		{
			for (int j = st[i] ; j <= ed[i] ; j ++)
			{
				if (a[j] == maxa[i])
				{
					maxa[i] = a[j];
				}
				sum[i] -= a[j];
				sum[i] += sqrt(a[j]);
				a[j] = sqrt(a[j]);
			}
			for (int j = st[i] ; j <= ed[i] ; j ++)
			{
				maxa[i] = max(maxa[i], a[j]);
			}
		}
	}
}

int cnt(int l, int r)
{
	int lb = block[l], rb = block[r], ans = 0;
	if (lb == rb)
	{
		for (int i = l ; i <= r ; i ++)
		{
			ans += a[i];
		}
		return ans;
	}
	for (int i = l ; i <= ed[lb] ; i ++)
	{
		ans += a[i];
	}
	for (int i = st[rb] ; i <= r ; i ++)
	{
		ans += a[i];
	}
	for (int i = lb + 1 ; i <= rb - 1 ; i ++)
	{
		ans += sum[i];
	}
	return ans;
}

int main()
{
	cin >> n;
	sq = sqrt(n);
	for (int i = 1 ; i <= n ; i ++)
	{
		scanf("%d", &a[i]);
		int s = i / sq + 1;
		if (!st[s])
		{
			st[s] = i;
		}
		ed[s] = i;
		sum[s] += a[i];
		maxa[s] = max(maxa[s], a[i]);
		block[i] = s;
	}
	int q;
	cin >> q;
	for (int i = 1 ; i <= q ; i ++)
	{
		int opt, l, r;
		scanf("%d%d%d", &opt, &l, &r);
		if (l > r)
		{
			swap(l, r);
		}
		if (!opt)
		{
			change(l ,r);
		}
		else
		{
			printf("%d\n", cnt(l, r));
		}
	}
}