#include <bits/stdc++.h>
using namespace std;
bool possible(int k, const vector<int>& a) {
multiset<int> ties;
for (int i = 0; i < k; ++i) {
ties.insert(1);
}
int consec_ignore = 0;
for (int x : a) {
auto it = ties.upper_bound(x);
if (it != ties.begin()) {
--it;
ties.erase(it);
ties.insert(x);
consec_ignore = 0;
} else {
consec_ignore++;
if (consec_ignore >= 2) {
return false;
}
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int left = 1, right = min(n, 40), ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (possible(mid, a)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << ans << endl;
return 0;
}
