#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
long long a[MAXN], sum[MAXN], tik[MAXN];
int L[MAXN], R[MAXN], pos[MAXN], n, m, t, add[MAXN];
void change(int l, int r) {
	int p = pos[l], q = pos[r];
	long long tot = 0;
	if (p == q) {
		for (int i = l; i <= r; ++i) tot += a[i] - (long long)floor(sqrt(a[i])), a[i] = sqrt(a[i]);
		sum[p] -= tot;
	} else {
		for (int i = p + 1; i <= q - 1; ++i) ++add[i];
		if (tik[p] > 0) { for (int i = l; i <= R[p]; ++i) tot += a[i] - (long long)floor(sqrt(a[i])), a[i] = sqrt(a[i]); sum[p] -= tot; }
		if (tik[q] > 0) { tot = 0; for (int i = L[q]; i <= r; ++i) tot += a[i] - (long long)floor(sqrt(a[i])), a[i] = sqrt(a[i]); sum[q] -= tot; }
	}
}
void chance(int addp, int i) {
	addp = min(addp, 6);
	while (addp--) {
		if (a[i] <= 1) return ;
		a[i] = (long long)floor(sqrt(a[i]));
	}
} 
long long ask(int l, int r) {
	int p = pos[l], q = pos[r];
	long long ans = 0, tot = 0;
	if (p == q) {
	    if (tik[p] > 0 && add[p] > 0) {
		    for (int i = L[p]; i <= R[p]; ++i) {
		    	long long now = a[i];
				chance(add[p], i);
				tot += now - a[i];
		    }
		    tik[p] -= add[p], add[p] = 0, sum[p] -= tot;
	    }
		for (int i = l; i <= r; ++i) ans += a[i];
	} else {
		for (int i = p + 1; i <= q - 1; ++i) {
			tot = 0;
		    if (tik[i] > 0 && add[i] > 0) {
			    for (int j = L[i]; j <= R[i]; ++j) {
			    	long long now = a[j];
				    chance(add[i], j);
				    tot += now - a[j];
			    }
				tik[i] -= add[i], add[i] = 0, sum[i] -= tot;
		    }
		    ans += sum[i];
		}
		tot = 0;
		if (tik[p] > 0 && add[p] > 0) {
		    for (int i = L[p]; i <= R[p]; ++i) {
				long long now = a[i];
				chance(add[p], i);
				tot += now - a[i];
			}
		    tik[p] -= add[p], add[p] = 0, sum[p] -= tot;
		}
		tot = 0;
		if (tik[q] > 0 && add[q] > 0) {
		    for (int i = L[q]; i <= R[q]; ++i) {
		    	long long now = a[i];
				chance(add[q], i);
				tot += now - a[i];
		    }
		    tik[q] -= add[q], add[q] = 0, sum[q] -= tot;
		}
		for (int i = l; i <= R[p]; ++i) ans += a[i];
		for (int i = L[q]; i <= r; ++i) ans += a[i];
	}
	return ans;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    t = sqrt(n);
    for (int i = 1; i <= t; ++i) {
		L[i] = (i - 1) * sqrt(n) + 1;
		R[i] = i * sqrt(n);
	}
	if (R[t] < n) ++t, L[t] = R[t - 1] + 1, R[t] = n;
	for (int i = 1; i <= t; ++i) {
	    for (int j = L[i]; j <= R[i]; ++j)
			pos[j] = i, sum[i] += a[j];
		tik[i] = 6;
	}
	scanf("%d", &m);
	while (m--) {
		int op, l, r;
		scanf("%d%d%d", &op, &l, &r);
		if (!op) change(l, r);
		else printf("%lld\n", ask(l, r));
	}
    return 0;
}

hack和#1~5AC

#6~10WA