Language: C++

#include <iostream>
#include <vector>
using namespace std;

template<class value_type, class size_type = size_t>
class RunLengthArray {
	using T = value_type;
	using S = size_type;

	vector<T> value;
	vector<pair<S, S>> index; // [first, second)

	size_t find(S i) {
		int left = 0, right = value.size();
		while (right - left > 1) {
			int mid = left + (right - left) / 2;
			(index[mid].first <= i ? left : right) = mid;
		}
		return left;
	}

public:
	RunLengthArray() {}
	RunLengthArray(const T& val, S size) :value({ val }), index({ {0,size} }) {}
	RunLengthArray(const initializer_list<pair<S, T>>& v) {
		index.reserve(v.size());
		value.reserve(v.size());
		S now = 0;
		for (const auto& p : v) {
			index.emplace_back(now, now + p.first);
			value.push_back(p.second);
			now += p.first;
		}
	}
	S size()const { return empty() ? 0 : index.back().second; }
	bool empty()const { return value.empty() || index.empty(); }
	explicit operator bool()const { return !empty(); }

	const T& operator[](const S i)const {
		assert(i < size());
		return value[find(i)];
	}
	const T& front()const {
		assert(!empty());
		return value.front();
	}
	const T& back()const {
		assert(!empty());
		return value.back();
	}

	pair<T, S> at(const size_t i)const {
		return make_pair(value[i], index[i].second - index[i].first);
	}
	size_t value_size()const {
		return value.size();
	}

	void clear() { value.clear(); index.clear(); }
	RunLengthArray& push_back(const T& val, const S new_size = 1) {
		if (empty() || value.back() != val) {
			value.push_back(val);
			index.emplace_back(size(), size() + new_size);
		} else {
			index.back().second += new_size;
		}
		return *this;
	}
	RunLengthArray& pop_back(const S pop_size = 1) {
		assert(pop_size <= size());
		S until = size() - pop_size;
		while (!empty()) {
			if (index.back().first == until) {
				value.pop_back();
				index.pop_back();
				break;
			} else if (index.back().first <= until && until < index.back().second) {
				index.back().second = until;
				break;
			} else {
				value.pop_back();
				index.pop_back();
			}
		}
		return *this;
	}
};


using ll = long long;

bool increment(RunLengthArray<ll, ll>& v, ll k) {
	if (v.value_size() == 1 && v.front() == k - 1) {
		return false;
	}

	if (v.back() < k - 1) {
		ll val = v.back();
		v.pop_back().push_back(val + 1);
	} else {
		ll len = v.at(v.value_size() - 1).second;
		v.pop_back(len);
		ll val = v.back();
		v.pop_back().push_back(val + 1).push_back(0, len);
	}
	return true;
}

int main() {
	int n; cin >> n;
	vector<ll> a(n);
	for (ll& i : a)cin >> i;

	auto check = [&](ll k) {
		RunLengthArray<ll, ll> v;
		v.push_back(0, a[0]);
		for (int i = 1; i < n; ++i) {
			if (a[i - 1] < a[i]) {
				v.push_back(0, a[i] - a[i - 1]);
			} else {
				if (a[i - 1] > a[i]) {
					v.pop_back(a[i - 1] - a[i]);
				}
				if (!increment(v, k))return false;
			}
		}
		return true;
	};

	if (check(1)) {
		cout << 1 << endl;
		return 0;
	}
	ll ng = 1, ok = 1e9;
	while (ok - ng > 1) {
		ll mid = (ng + ok) / 2;
		(check(mid) ? ok : ng) = mid;
	}
	cout << ok << endl;
}

Compiler output:
a.cc: In instantiation of 'const RunLengthArray<value_type, size_type>::T& RunLengthArray<value_type, size_type>::front() const [with value_type = long long int; size_type = long long int; T = long long int]':
a.cc:93:36:   required from here
   93 |         if (v.value_size() == 1 && v.front() == k - 1) {
      |                                    ~~~~~~~^~
a.cc:44:23: error: 'assert' was not declared in this scope
   44 |                 assert(!empty());
      |                 ~~~~~~^~~~~~~~~~
a.cc:3:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
    2 | #include <vector>
  +++ |+#include <cassert>
    3 | using namespace std;
a.cc: In instantiation of 'const RunLengthArray<value_type, size_type>::T& RunLengthArray<value_type, size_type>::back() const [with value_type = long long int; size_type = long long int; T = long long int]':
a.cc:97:12:   required from here
   97 |         if (v.back() < k - 1) {
      |             ~~~~~~^~
a.cc:48:23: error: 'assert' was not declared in this scope
   48 |                 assert(!empty());
      |                 ~~~~~~^~~~~~~~~~
a.cc:48:23: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
a.cc: In instantiation of 'RunLengthArray<value_type, size_type>& RunLengthArray<value_type, size_type>::pop_back(S) [with value_type = long long int; size_type = long long int; S = long long int]':
a.cc:99:13:   required from here
   99 |                 v.pop_back().push_back(val + 1);
      |                 ~~~~~~~~~~^~
a.cc:70:23: error: 'assert' was not declared in this scope
   70 |                 assert(pop_size <= size());
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~
a.cc:70:23: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'