-
首先随便想个暴力，对于 \(a_i > a_{i -1}\)，我们直接往字符串的末尾加上一些最小的字符。对于 \(a_i \le a_{i - 1}\)，我们保留前缀之后随便加一个位置的 \(1\)。
-
发现这个随便的位置不是很好找，于是想到用二分转枚举为判断。二分最大的字符（可以转化为数字）\(x\)，每次我们只往最后一位加一，这相当于在 \(x\) 进制下做一个加法。
-
注意二分的判断错误的条件，当第一位产生进位时，前面已经没有位置了，于是无解。
-
注意到 \(a_i\) 很大，直接做加法会炸。我们不妨去除重复状态，只记录不为 \(0\) 的数，如果这些数中没有加一的数就添一个数进来。这样由于每次最多添一个数，所以空间复杂度为 \(O(n)\)。时间复杂度为 \(O(n\log n)\)。这里的 \(\log\) 来自二分。
-
实现的细节写在代码里了。
/*
教学局，必拿下
更新分三步走：删后缀，进位，加数。
于是我们需要一个支持查询，删除，加入，更改值，下标还很大的东西。很容易想到 map。
将 map 的 first 作位，second 存值，直接更新即可。
注意到只有当 a[i]>=a[i-1] 时才会更新，所以把超过的后缀删掉这一步可以直接从最后开始删。因为里面加入的元素 first 递增。
这样理论复杂度会上升一个 log，应该还是能过的，但我被卡了 －_－b
注意到上上行的发现，想到用栈代替 map，果然快的一批
*/
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
const long long N = 2e5+5, mod = 998244353;
int n;
int a[N];
#define id first
#define w second
bool check(int x) {
stack<pair<int, int>> sta;
for (int i = 2; i <= n; ++i)
if (a[i] <= a[i - 1]) {
while (!sta.empty()) {
int l = sta.top().id;
if (l > a[i]) sta.pop();
else break;
}
int l = a[i];
while (((!sta.empty() && sta.top().id == l && sta.top().w + 1 == x) || x == 1) && l > 0) {
if (!sta.empty()) sta.pop();
--l;
}
if (l == 0)
return false;
int val = 0;
if (!sta.empty() && sta.top().id == l) val = sta.top().w;
++val;
if (!sta.empty() && sta.top().id == l) sta.pop();
sta.push(make_pair(l, val));
}
return true;
}
#undef id
#undef w
signed main(){
freopen("text.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
int l = 1, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid) == true) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}