#include <iostream>
#include <algorithm>
/*
we have something which stores how many elements we have at the back
*/
#define MAXN 500005
#define int long long
#define printf
int a[MAXN];
int occ[MAXN];
int occn = 0;
int occe = 0;
signed main()
{
int n;
std::cin >> n;
int case_three = 0;
for (int i = 1; i <= n; ++i)
{
std::cin >> a[i];
case_three = case_three && (a[i] == 1 || a[i] == 2);
}
int amount = 0;
for (int i = n; i >= 1 && a[i] == 2; --i) ++amount;
printf("amount: %i\n", amount);
for (int i = 1; i <= n-amount; ++i)
{
if (a[i] == 2)
{
occ[++occn] = i;
printf("occ[%i] = %i\n", occn, occ[occn]);
}
}
occ[++occn] = n-amount+1;
printf("occ[%i] = %i\n", occn, occ[occn]);
int q;
std::cin >> q;
while (q--)
{
int t;
std::cin >> t;
if (t == 1)
{
if (occe >= occn-1) continue;
++occe;
}
else
{
int l, r;
std::cin >> l >> r;
int twos = 0;
if (occe < occn-1)
{
// the first index k such that data[k] - occe >= l <=> data[k] >= l + occe
// the last index k such that data[k] - occe <= r <=> data[k] <= r + occe
auto up = std::lower_bound(occ+occe+1, occ+occn, l + occe);
auto down = std::upper_bound(occ+occe+1, occ+occn, r + occe);
int hm = down - up;
twos += hm;
printf("bounds result: %i\n", hm);
}
int count_to = n - amount - occe + 1;
twos += std::min(r - l + 1, std::max((int)0, r - count_to + 1));
printf("count to: %i; twos=%i\n", count_to, twos);
std::cout << r - l + 1 + twos << "\n";
}
}
return 0;
}
