#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
#define INF (int)(1e18)
struct query_t
{
int t, l, r;
};
int a[MAXN];
int occ[MAXN];
query_t queries[MAXN];
int occn = 0;
int occe = 0;
int n, q;
int pref[MAXN];
signed main1()
{
for (int i = 1; i <= n; ++i)
{
pref[i] = pref[i-1] + a[i];
}
for (int qp = 1; qp <= q; ++qp)
{
int t = queries[qp].t;
if (t == 1)
{
for (int j = 1; j <= n-1; ++j)
{
if (a[j] > a[j+1]) std::swap(a[j], a[j+1]);
pref[j] = pref[j-1] + a[j];
}
}
else
{
int l = queries[qp].l, r = queries[qp].r;
std::cout << pref[r] - pref[l-1] << "\n";
}
}
return 0;
}
signed main3()
{
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]);
for (int qp = 1; qp <= q; ++qp)
{
// printf("%i, %i\n", qp, q);
int t = queries[qp].t;
if (t == 1)
{
if (occe >= occn-1) continue;
++occe;
}
else
{
int l = queries[qp].l, r = queries[qp].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;
}
int pmin[MAXN];
int q1cnt;
signed main2()
{
pmin[0] = INF;
for (int i = 1; i <= n; ++i)
{
pmin[i] = std::min(pmin[i-1], a[i]);
}
q1cnt = 1;
for (int qp = 1; qp <= q; ++qp)
{
int t = queries[qp].t;
if (t == 1)
{
++q1cnt;
q1cnt = std::min(q1cnt, n);
}
else
{
std::cout << pmin[q1cnt] << "\n";
}
}
return 0;
}
int seg[4*MAXN];
void build(int l=1, int r=n, int si=1)
{
if (l == r)
{
seg[si] = a[l];
return;
}
int m = (l+r)/2;
build(l, m, 2*si);
build(m+1, r, 2*si+1);
seg[si] = std::min(seg[2*si], seg[2*si+1]);
}
int query(int ql, int qr, int l=1, int r=n, int si=1)
{
if (ql <= l && r <= qr) return seg[si];
int m = (l+r)/2;
if (ql <= m && m+1 <= qr) return std::min(query(ql, qr, l, m, 2*si), query(ql, qr, m+1, r, 2*si+1));
if (ql <= m) return query(ql, qr, l, m, 2*si);
return query(ql, qr, m+1, r, 2*si+1);
}
signed main4()
{
// query at L=R=i is min[i...i+op1]
build();
int q1cnt = 0;
for (int qp = 1; qp <= q; ++qp)
{
int t = queries[qp].t;
if (t == 1)
{
++q1cnt;
}
else
{
int idx = queries[qp].l;
int ep = std::min(idx + q1cnt, n);
std::cout << query(idx, ep) << "\n";
}
}
return 0;
}
signed main()
{
std::cin >> n;
int case_three = 1;
for (int i = 1; i <= n; ++i)
{
std::cin >> a[i];
case_three = case_three && (a[i] == 1 || a[i] == 2);
}
std::cin >> q;
int q1c = 0;
int case_two = 1;
int case_four = 1;
for (int i = 1; i <= q; ++i)
{
std::cin >> queries[i].t;
if (queries[i].t == 2)
{
std::cin >> queries[i].l >> queries[i].r;
case_two = case_two && (queries[i].l == 1 && queries[i].r == 1);
case_four = case_four && (queries[i].l == queries[i].r);
}
else ++q1c;
}
int case_one = q1c <= 10;
if (case_three)
{
return main3();
}
else if (case_two)
{
printf("detected!\n");
return main2();
}
else if (case_four)
{
printf("detected case four!\n");
return main4();
}
else if (case_one)
{
return main1();
}
return 0;
}
