二分,注意关键

#include<iostream>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
ll n, Max;
ll a[N];
bool check(ll x) {
	for (int i = 1; i <= n; ++i) {
		if (a[i] > x)x -= a[i] - x;
		else x += x - a[i];
		if (x < 0) return false;
		if (x >= Max)return true;//关键
	}
	return true;
}
int main() {
	scanf("%lld", &n);
	for (ll i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		if (a[i] > Max)Max = a[i];
	}
	ll l = 0, r = Max, mid;
	while (l < r) {
		mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%lld\n", r);
	return 0;
}