#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5 + 100;
const int MOD = 1e9 + 7;
const int L = 30;

vector<deque<pii>> f(deque<pii> a, deque<pii> b){
	// cout << "MERGING ";
	// for(pii x: a) cout << x.first << ' ' << x.second << ", ";
	// cout << " AND ";
	// for(pii x: b) cout << x.first << ' ' << x.second << ", ";
	// cout << endl;;
	while(a.size() && b.size()){
		if(a.back().first == b.front().first){
			a.back().second += b.front().second;
			b.pop_front();
			continue;
		}
		pii x;
		if(a.back() < b.front()){
			if(a.size() == 1 || a[a.size()-2] < a.back()) break;
			x = a.back(); a.pop_back();
		} else{
			if(b.size() == 1 || b[1] < b[0]) break;
			x = b.front(); b.pop_front();
		}
		if(x.second & 1){
			x.second--;
			if(x.second){
				a.push_back(x);
				b.push_front(x);
			}
			// cout << "MERGED" << endl;
			return {a, b};
		}
		x.second >>= 1;
		x.first++;
		if(a.back().first == x.first){
			a.back().second += x.second;
		} else a.push_back(x);
	}
	// cout << "MERGED" << endl;
	for(int i = 0; i < b.size(); i++){
		a.push_back(b[i]);
	}
	return {a};
}

int get(deque<pii> &a){
	// cout << "CALCULATING ";
	// for(pii x: a) cout << x.first << ' ' << x.second << ", ";
	// cout << endl;
	pii left = {0, 0};
	int m = 0;
	while(m + 1 < a.size() && a[m+1].first > a[m].first) m++;
	for(int i = 0; i <= m; i++){
		while(left.first < a[i].first){
			left.first++; left.second >>= 1;
		}
		left.second += a[i].second;
	}
	pii right = {0, 0};
	for(int i = a.size() - 1; i > m; i--){
		while(right.first < a[i].first){
			right.first++;
			right.second >>= 1;
		}
		right.second += a[i].second;
	}
	while(right.first < left.first){
		right.first++;
		right.second >>= 1;
	}
	while(right.first > left.first){
		left.first++;
		left.second >>= 1;
	}
	left.second += right.second;
	while(left.second > 1){
		left.second /= 2;
		left.first++;
	}
	// cout << "CALCULATED" << endl;
	return left.first;
}

int n;
int a[N];
struct asd{
	int ans;
	deque<pii> a, b;
	bool ok;
} d[N * 4];

void calc(asd &a, asd &b, asd &c){
	c.ans = max(a.ans, b.ans);
	vector<deque<pii>> x = f(a.b, b.a);
	for(auto &i: x) c.ans = max(c.ans, get(i));
	c.ok = a.ok & b.ok & (x.size()==1);
	if(a.ok) c.a = x[0];
	else c.a = a.a;
	if(b.ok) c.b = x.back();
	else c.b = b.b;
}

void build(int v = 1, int tl = 1, int tr = n){
	if(tl == tr){
		d[v].ans = a[tl]; d[v].ok = 1;
		d[v].a = d[v].b = {{a[tl], 1}};
	} else{
		int mid = (tl + tr) >> 1;
		build(v<<1, tl, mid);
		build(v<<1|1, mid+1, tr);
		calc(d[v<<1], d[v<<1|1], d[v]);
	}
}

void upd(int i, int x, int v = 1, int tl = 1, int tr = n){
	if(tl == tr){
		a[tl] = x;
		d[v].ans = a[tl]; d[v].ok = 1;
		d[v].a = d[v].b = {{a[tl], 1}};
	} else{
		int mid = (tl + tr) >> 1;
		if(i <= mid) upd(i, x, v<<1, tl, mid);
		else upd(i, x, v<<1|1, mid+1, tr);
		calc(d[v<<1], d[v<<1|1], d[v]);
	}
}

asd res;
void get(int l, int r, int v = 1, int tl = 1, int tr = n){
	if(tr < l || tl > r) return;
	if(l <= tl && tr <= r) calc(res, d[v], res);
	else{
		int mid = (tl + tr) >> 1;
		get(l, r, v<<1, tl, mid);
		get(l, r, v<<1|1, mid+1, tr);
	}
}

void prepare_game(vector<int> A) {
    n = A.size();
    for(int i = 1; i <= n; i++) {
        a[i] = A[i-1];
    }
    // cout << "PREPARE GAME" << endl;
    build();
    // cout << "BUILD DONE" << endl;
}

int play_game(int l, int r) {
	l++; r++;
	res = {0, {}, {}, 1};
	get(l, r);
	// cout << "GAME DONE" << endl;

	return res.ans;
}

void update_game(int i, int x) {
	i++;
	upd(i, x);
	// cout << "UPDATE DONE" << endl;
}

#ifndef ONLINE_JUDGE
//код от #ifndef ONLINE_JUDGE до #endif не будет запускатся в системе
int main(void)
{
    // freopen("input.in", "r", stdin);
    //	freopen("out.out","w",stdout);
    int n; cin >> n;
    vector<int> a;
    for(int i = 1; i <= n; i++) {
        a.push_back(0);
        cin >> a.back();
    }
    prepare_game(a);
    int q; cin >> q;
    while(q--) {
        int t; cin >> t;
        if(t == 1) {
            int i, x;
            cin >> i >> x;
            update_game(i, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << play_game(l, r) << "\n";
        }
    }
}
#endif