#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e3 + 10, inf = 1e15;

int n, idx, l[N], r[N], a[N], s[N], sz[N], rx[N], rs[N];

struct F
{
	int i, j;
	
	bool operator> (const F& f2) const
	{
		return i * f2.j > j * f2.i;
	}
	
}ans[N];

int dp[N][N], tmp[N];
vector<int> son[N];
vector<int> rg[N];
map<array<int, 2>, int> mp;

int build(int l, int r)
{
	idx++, ::l[idx] = l, ::r[idx] = r, mp[{l, r}] = idx;
	sz[idx] = 1;
	int x = idx; rx[x] = r - l + 1, rs[x] = s[r] - s[l - 1];
	for (int i = l; i <= r; i++)
	{
		if (rg[i].empty()) continue;
		int j = rg[i].back(); rg[i].pop_back();
		int y = build(i, j);
		son[x].push_back(y);
		rx[x] -= (j - i + 1), rs[x] -= (s[j] - s[i - 1]);
		i = j;
	}
	return x;
}

template<class T>
void chkmax(T &x, T y)
{
	if (y > x) x = y;
}

void dfs(int x)
{
	if (n > 250) return;
	for (int i = 0; i <= n; i++) dp[x][i] = -inf;
	dp[x][rx[x]] = rs[x];
	sz[x] = rx[x];
	for (int y : son[x])
	{
		dfs(y);
		for (int i = 0; i <= sz[x] + sz[y]; i++) tmp[i] = -inf;
		for (int i = 0; i <= sz[x]; i++)
			for (int j = 0; j <= sz[y]; j++)
				chkmax(tmp[i + j], dp[x][i] + dp[y][j]);
		for (int i = 0; i <= sz[x] + sz[y]; i++) dp[x][i] = tmp[i];
		sz[x] += sz[y];
 	}
 	chkmax(dp[x][0], 0ll);
}

void initialize(vector<signed> A)
{
    n = (int)(A.size());
    for (int i = 1; i <= n; i++) a[i] = A[i - 1];
	for (int i = 1; i <= n; i++) s[i] = a[i] + s[i - 1];
    vector<int> s;
    for (int i = n; i >= 1; i--)
    {
    	while (!s.empty() && a[s.back()] > a[i])
    	{
    		int x = s.back(); s.pop_back();
    		if (x != i + 1) rg[i + 1].push_back(x - 1);
    	}
    	if (!s.empty() && s.back() != i + 1) rg[i + 1].push_back(s.back() - 1); 
    	if (!s.empty() && a[s.back()] >= a[i]) s.pop_back();
    	s.push_back(i);
    }
//	for (int i = 1; i <= n; i++)
//		for (int j : rg[i]) printf("[%lld, %lld]\n", i, j);
    
    build(2, n - 1);
//    for (int i = 1; i <= n; i++)
//    	printf("rx[%lld] = %lld, rs[%lld] = %lld\n", i, rx[i], i, rs[i]);
    
    dfs(1);
    
//    for (int i = 1; i <= n; i++)
//    	for (int j = 0; j <= sz[i]; j++)
//    		printf("dp[%lld][%lld] = %lld\n", i, j, dp[i][j]);
    
    for (int i = 1; i <= n; i++)
    {
    	ans[i] = {0, 1};
    	for (int j = 0; j <= sz[i]; j++)
			chkmax(ans[i], F{dp[i][j] + a[l[i] - 1] + a[r[i] + 1], j + 2});    
		int d = __gcd(ans[i].i, ans[i].j);
		ans[i].i /= d, ans[i].j /= d;
	}
//    for (int i = 1; i <= n; i++)
//    	for (int j : son[i]) printf("[%lld, %lld] -> [%lld, %lld]\n", l[i], r[i], l[j], r[j]);
}

array<long long, 2> maximum_average(signed i, signed j)
{
	i++, j++;
	if (j == i + 1) return {a[i] + a[j], 2};
	assert(mp.find({i + 1, j - 1}) != mp.end());
	int id = mp[{i + 1, j - 1}];
	return {ans[id].i, ans[id].j};
}

//signed main()
//{
//	int n; cin >> n;
//	vector<signed> A;
//	for (int i = 1, ai; i <= n; i++) cin >> ai, A.push_back(ai); 
//	initialize(A);
//	while (1)
//	{
//		int l, r; cin >> l >> r;
//		auto res = maximum_average(l, r);
//		cout << res[0] << ' ' << res[1] << endl;
//	}
//}