#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3e5 + 10, inf = 1e13;

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

#define __int128 int

struct F
{
	int i, j;
	
	F()
	{
		i = j = 0;
	}
	
	F(int a, int b)
	{
		int d = __gcd(a, b);
		i = a / d, j = b / d;
	}
	
	bool operator> (const F& f2) const
	{
		return (__int128)i * f2.j > (__int128)j * f2.i;
	}
	
	bool operator< (const F& f2) const
	{
		return (__int128)i * f2.j < (__int128)j * f2.i;
	}
	
	F operator + (const F& f2) const
	{
		__int128 a = (__int128)i * f2.j + (__int128)j * f2.i, b = (__int128)j * f2.j;
		auto d = __gcd(a, b);
		return {a / d, b / d};
	}
	
	void reduce()
	{
		auto d = __gcd(i, j);
		i /= d, j /= d;
	}
	
}ans[N];

struct DS
{
	vector<F> d;
	
	void insert(F v) 
	{
		d.insert(lower_bound(d.begin(), d.end(), v), v);
	}
	
	void assign(int pos, F v)
	{
		assert(pos < d.size());
		for (int i = 1; i <= pos; i++) d[i] = v;
	}
	
	F operator[] (int x) const
	{
		F s = {0, 1};
		for (int i = 0; i < x; i++) s = s + d[i];
		return s;
	}
	
};

DS ds[N];
DS* dp[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;
}

DS* merge(DS* a, DS* b)
{
	if (a->d.size() < b->d.size()) swap(a, b);
	for (F v : b->d) a->insert(v);
	return a;
}
pair<int, F> getp(const DS* ds, int a, int b)
{
	// argmax (y - b) / (x - a)
	assert(!ds->d.empty());
	int l = 0, r = ds->d.size() - 1;
	auto getres = [&](int x)
	{
		F y1 = (*ds)[x];
		y1.i -= b * y1.j, y1.j *= (x - a);
		return y1;
	};
	while (l + 1 < r)
	{
		int mid1 = l + (r - l + 1) / 3, mid2 = r - (r - l) / 3;
		F y1 = getres(mid1), y2 = getres(mid2);
		if (y1 < y2) l = mid1 + 1;
		else if (y1 > y2) r = mid2 - 1;
		else l = mid1, r = mid2;
	}
	if (getres(l) > getres(r)) return {l, getres(l)};
	else return {r, getres(r)};
}

void dfs(int x)
{
	if (son[x].empty())
	{
		dp[x] = &ds[x];
		if (rx[x]) for (int i = 1; i <= rx[x]; i++) dp[x]->insert({rs[x], rx[x]});
		return;
	}
	
	dp[x] = &ds[0];
	for (int y : son[x]) dp[x] = merge(dp[x], dp[y]);
	// (-rx[x], -rs[x])
	auto res = getp(dp[x], -rx[x], -rs[x]);
	int p = res.first;
	F v = res.second;
	dp[x]->assign(p, v);
	for (int i = 1; i <= rx[x]; i++) dp[x]->insert(v);
	
	res = getp(dp[x], -2, -(a[l[x] - 1] + a[r[x] + 1]));
	ans[x] = res.second;
}

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++)
//    	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;
//	}
//}