#12008 262144

gold 에 있는 n<=248 인 버젼은 쉽게 할 수 있었다.
O(n^3)구간 dp를 짜주면 된다.

 

이 문제는 재밌게 풀었는데, 잘 알려진 거와 다르게 sparse table이나 dp를 사용하지 않고도 쉽게 풀 수 있다.

우선 관찰하기 가장 쉬운 포인트는 1이상 40이하의 정수로 이루어져 있다는 점이다.

 

이제 문제를 풀어보자.

특정 구간 [l , r]을 잡아서 이에 속한 연속된 구간을 적당히 합쳐서 단 하나의 수로 만들 수 있을 때,

이 구간을 "좋은 구간"이라고 하자.

그리고 마지막에 남는 하나의 정수를 "좋은 구간의 값"이라고 하자.

 

문제를 풀며 다음의 사실들을 관찰했다.

 

Q : 특정한 좋은 구간에서 만들 수 있는 수는 유일한가?

A : 유일하다.

 

Q : 시작점을 고정시키고 나서의 좋은 구간은 연속적인가?

A : 연속적이지 않다 --> binary search 불가

 

Q : 시작점을 고정시켰을 때 길이가 클 수록 좋은 구간의 값은 커지는가?

A : 커진다.

 

그렇다면 다음 2가지 sub문제로 바꿔보자.

1. 특정 구간이 주어졌을 때 이 구간이 좋은 구간인지를 어떻게 판정할 것인가?

2. 좋은 구간이 주어졌을 때 이 구간의 값을 어떻게 판정할 것인가?

 

1번은 의외로 쉽게 할 수 있는데, 구간을 정렬하고, 앞에서 부터 합쳐주면서 홀 수 component가 되지 않으면 된다.

이 풀이의 정당성은 쉽게 증명 된다.

 

2번도 1번에서 파생되어 나온다.

합쳐나가면서 마지막으로 남는 수가 구간의 값이라는 것을 쉽게 알 수 있다.

 

그렇다면 본 문제를 풀어보자.

이제 핵심 아이디어는 1~39 까지 i를 순회하면서 i가 1일때는 연속된 1들을 합쳐 줄 것이라는 점이다.

 

예를 들어서 [1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 2] 이라는 구간은 다음과 같이 합칠 수 있다.

한번 합치면 [2, 2, 3, 2, 2, 2, 2]

두번 합치면 [3, 3, 3, 3]

세번 합치면 [6, 6]

마지막으로 [12]가 되어서. 이 좋은 구간의 값은 12이다.

 

그런데 [2, 1, 1, 1, 2]같은 경우는 문제가 된다. 연속된 1이 홀수개이기 때문인데, 이때는 다음과 같이 나눠준다.

[2, 2, -1, 2, 2] 좋은 구간이 끊어지기 때문이다.

따라서 이런식으로 하게 되면 마지막에는 

[mx,mx,mx, ... -1 , mx ... -1,mx]이런식으로 원래 구간의 최댓값인 mx와 -1로만 이루어진 구간으로 바뀌게 된다.

이때, mx로 이루어진 최대 수열의 길이를 찾으면 문제를 풀 수 있다.

#include<bits/stdc++.h>
//#define double long double
//T.erase(unique(T.begin(),T.end()),T.end());
//written by djs100201
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 3e5 + 100, inf = (ll)1e9 * (ll)1e9 + 7, mod = 1e9 + 7, sqrtN = 320;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, base, ans, q;
ll gcd(ll x, ll y) {
	if (!y)return x;
	return gcd(y, x % y);
}
void solve() {
	vector<P>v;
	cin >> n;
	c = inf;
	for (int i = 0; i < n; i++) {
		cin >> a;
		b = max(b, a);
		c = min(c, a);
		if (v.empty() || v.back().first != a)v.push_back({ a,1 });
		else v.back().second++;
	}
	for (int i = c; i < b; i++) {
		vector<P>T;
		for (auto nxt : v) {
			if (nxt.first != i) {
				if (T.empty() || T.back().first != nxt.first)T.push_back(nxt);
				else T.back().second += nxt.second;
			}
			else {
				a = nxt.second / 2;
				if (nxt.second & 1) {
					if (T.empty() || T.back().first != nxt.first + 1)T.push_back({ nxt.first + 1,a });
					else T.back().second += a;
					if (T.empty() || T.back().first != -1)T.push_back({-1,-1e13 });

					if (T.empty() || T.back().first != nxt.first + 1)T.push_back({ nxt.first + 1,a });
					else T.back().second += a;
				}
				else {
					if (T.empty() || T.back().first != nxt.first + 1)T.push_back({ nxt.first + 1,a });
					else T.back().second += a;
				}
			}
		}
		swap(v, T);
	}
	for (auto nxt : v) {
		if (nxt.first == -1) {
			sum = 0;
			continue;
		}
		sum += nxt.second;
		ans = max(ans, sum);
	}
	while (ans >= 2) {
		b++;
		ans /= 2;
	}
	cout << b << endl;

}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//cin >> tc;
	while (tc--)solve();
}