// MagicDark
#include <bits/stdc++.h>
#define deque vector
#define mid ((l + r) >> 1)
#define ls num << 1
#define rs ls | 1
#define li ls, l, mid
#define ri rs, mid + 1, r
#define debug cerr << "\033[32m[" << __LINE__ << "]\033[0m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
const int N = 1e5 + 10;
int n, a[N], q;
struct Node {
	bool flag;
	int ans;
	deque <pair <int, int>> tl, tr;
} info[N << 2];
int lg(int x) {return 31 ^ __builtin_clz(x);}
int calc(deque <pair <int, int>> x) {
	while (x.size() > 1) {
		if (x.front().first < x.back().first) {
			auto [a, b] = x.front(); x.erase(x.begin());
			a++, b /= 2;
			if (x.size() && x.front().first == a) x.front().second += b;
			else x.insert(x.begin(), make_pair(a, b));
		} else {
			auto [a, b] = x.back(); x.pop_back();
			a++, b /= 2;
			if (x.size() && x.back().first == a) x.back().second += b;
			else x.push_back(make_pair(a, b));
		}
	}
	return x.front().first + lg(x.front().second);
}
bool g;
deque <pair <int, int>> ta, tb, tc;
deque <pair <int, int>> rev(deque <pair <int, int>> x) {
	reverse(all(x));
	return x;
}
deque <pair <int, int>> dot(deque <pair <int, int>> x) {
	while (x.size() > 1 && x.back().first < x[SZ(x) - 1].first) {
		auto [a, b] = x.back(); x.pop_back();
		a++, b /= 2;
		if (x.size() && x.back().first == a) x.back().second += b;
		else x.push_back(make_pair(a, b));
	}
	return x;
}
bool work(deque <pair <int, int>> x, deque <pair <int, int>> y) {
	deque <pair <int, int>> ans;
	while (x.size() && y.size()) {
		if (x.back().first == y.front().first) {
			x.back().second += y.front().second;
			y.erase(y.begin());
		} else if (x.back().first < y.front().first) {
			if (x.size() == 1 || x[SZ(x) - 1].first < x.back().first) break;
			if (x.back().second & 1) {
				auto w = x.back();
				y.insert(y.begin(), w);
				ta = x, tb = y;
				// auto [a, b] = x.back(); x.pop_back();
				// a++, b /= 2;
				// if (x.size() && x.back().first == a) x.back().second += b;
				// else x.push_back(make_pair(a, b));
				return true;
			} else {
				auto [a, b] = x.back(); x.pop_back();
				a++, b /= 2;
				if (x.size() && x.back().first == a) x.back().second += b;
				else x.push_back(make_pair(a, b));
			}
		} else {
			if (y.size() == 1 || y[1].first < y.front().first) break;
			if (y.front().second & 1) {
				auto w = y.front();
				x.push_back(w);
				ta = x, tb = y;
				// auto [a, b] = x.back(); x.pop_back();
				// a++, b /= 2;
				// if (x.size() && x.back().first == a) x.back().second += b;
				// else x.push_back(make_pair(a, b));
				return true;
			} else {
				auto [a, b] = y.front(); y.erase(y.begin());
				a++, b /= 2;
				if (y.size() && y.front().first == a) y.front().second += b;
				else y.insert(y.begin(), make_pair(a, b));
			}
		}
	}
	ta = x, tb = y;
	return false;
}
Node operator + (Node x, Node y) {
	Node z;
	z.ans = max(x.ans, y.ans);
	if (x.flag && y.flag) {
		z.flag = true;
		z.tl = x.tl, z.tr = y.tr;
		// deque <pair <int, int>> tt;
		// reverse(all(x.tr));
		// for (auto i: x.tr) tt.push_back(i);
		// for (auto i: y.tl) tt.push_back(i);
		if (work(x.tr, y.tl)) {
			chkmax(z.ans, calc(ta));
			chkmax(z.ans, calc(tb));
		} else {
			deque <pair <int, int>> tt = ta;
			for (auto i: tb) tt.push_back(i);
			chkmax(z.ans, calc(tt));
		}
		// chkmax(z.ans, calc(tt));
	}
	if (x.flag && !y.flag) {
		z.flag = true;
		z.tl = x.tl;
		if (work(x.tr, y.tl)) {
			chkmax(z.ans, calc(ta));
			z.tr = rev(dot(rev(tb)));
		} else {
			z.tr = ta;
			for (auto i: tb) z.tr.push_back(i);
			z.tr = rev(dot(rev(z.tr)));
		}
	}
	if (!x.flag && y.flag) {
		z.flag = true;
		z.tr = y.tr;
		if (work(x.tl, y.tl)) {
			chkmax(z.ans, calc(tb));
			z.tl = dot(ta);
		} else {
			z.tl = ta;
			for (auto i: tb) z.tl.push_back(i);
			z.tl = dot(z.tl);
		}
	}
	if (!x.flag && !y.flag) {
		if (work(x.tl, y.tl)) {
			z.flag = true;
			z.tl = dot(ta);
			// reverse(all(tb));
			z.tr = rev(dot(rev(tb)));
		} else {
			z.flag = false;
			z.tl = ta;
			for (auto i: tb) z.tl.push_back(i);
		}
	}
	return z;
}
void pushup(int num) {
	// debug << "~ " << (ls) << " " << (rs) << endl;
	info[num] = info[ls] + info[rs];
}
void init(int num, int x) {
	info[num].flag = false;
	info[num].ans = a[x];
	info[num].tl.clear();
	info[num].tr.clear();
	info[num].tl.emplace_back(a[x], 1);
}
void build(int num, int l, int r) {
	if (l == r) {
		init(num, l);
		return;
	}
	build(li), build(ri);
	pushup(num);
}
void modify(int num, int l, int r, int x) {
	if (l == r) {
		init(num, l);
		return;
	}
	if (mid >= x) modify(li, x);
	else modify(ri, x);
	pushup(num);
}
Node query(int num, int l, int r, int L, int R) {
	if (L <= l && r <= R) return info[num];
	if (mid >= R) return query(li, L, R);
	if (mid < L) return query(ri, L, R);
	return query(li, L, R) + query(ri, L, R);
}
void prepare_game(vector<int>A) {
	n = A.size();
	F(i, 1, n) a[i] = A[i - 1];
	build(1, 1, n);
}
int play_game(int x, int y) {
	x++, y++;
	Node w = query(1, 1, n, x, y);
	chkmax(w.ans, calc(w.tl));
	if (w.flag) chkmax(w.ans, calc(w.tr));
	return w.ans;
}
void update_game(int x, int y) {
	x++;
	a[x] = y;
	modify(1, 1, n, x);
}
// signed main() {
// 	// freopen("seq.in", "r", stdin);
// 	// freopen("seq.out", "w", stdout);
// 	// return 0;
// 	read(q);
// 	while (q--) {
// 		int op, x, y; read(op), read(x), read(y);
// 		if (op == 2) {
// 			a[x] = y;
// 			modify(1, 1, n, x);
// 		} else {
// 			Node w = query(1, 1, n, x, y);
// 			chkmax(w.ans, calc(w.tl));
// 			if (w.flag) chkmax(w.ans, calc(w.tr));
// 			cout << w.ans << '\n';
// 		}
// 	}
// 	return 0;
// }
// /* why?
// */