#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3e5 + 10;

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

//#define __int128 int

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

namespace Tree
{
	mt19937 rng(20241015);
	
	const int R = 30;
	int idx;
	int ls[N * R], rs[N * R], sz[N * R];
	F tass[N * R];
	F val[N * R], sum[N * R];
	
	void init()
	{
		val[0] = sum[0] = {0, 1};
	}
	
	int newnode(F v)
	{
		idx++;
		assert(idx < N * R);
		ls[idx] = rs[idx] = 0, sz[idx] = 1, tass[idx] = {0, 1};
		val[idx] = sum[idx] = v;
		return idx;
	}
	
	inline void pushup(int u)
	{
		if (!u) return;
		sum[u] = sum[ls[u]] + val[u] + sum[rs[u]];
		sz[u] = sz[ls[u]] + 1 + sz[rs[u]];
	}
	
	inline void apply(int u, const F& dass)
	{
		if (!u) return;
		sum[u] = {dass.i * sz[u], dass.j}, sum[u].reduce(), val[u] = dass;
		tass[u] = dass;
	}
	
	inline void pushdown(int u)
	{
		if (!u) return;
		if (tass[u].i == 0) return;
		apply(ls[u], tass[u]), apply(rs[u], tass[u]);
		tass[u] = {0, 1};
	}
	
	array<int, 2> splitr(int u, int k)
	{
		// [1, k], [k+1, inf)
//		printf("splitr(%lld, %lld)\n", u, k);
		if (!u) return {0, 0};
		pushdown(u);
		if (sz[ls[u]] >= k)
		{
			auto res = splitr(ls[u], k);
			ls[u] = res[1];
			pushup(u);
			return {res[0], u};
		}
		else
		{
			auto res = splitr(rs[u], k - sz[ls[u]] - 1);
			rs[u] = res[0];
			pushup(u);
//			printf("&&&");
			return {u, res[1]};
		}
	}
	
	array<int, 2> splitv(int u, const F& v)
	{
		// [1, v] [v, inf)
		if (!u) return {0, 0};
		pushdown(u);
		if (v > val[u])
		{
			auto res = splitv(ls[u], v);
			ls[u] = res[1];
			pushup(u);
			return {res[0], u};
		}
		else
		{
			auto res = splitv(rs[u], v);
			rs[u] = res[0];
			pushup(u);
			return {u, res[1]};
		}
	}
	
	int merge(int l, int r)
	{
//		printf("merge(%lld, %lld)\n", l, r);
		if (!l) swap(l, r);
		if (!r) return l;
		
		pushdown(l), pushdown(r);
		if (rng() % (sz[l] + sz[r]) < sz[l])
		{
			rs[l] = merge(rs[l], r);
			pushup(l);
			return l;
		}
		else
		{
			ls[r] = merge(l, ls[r]);
			pushup(r);
			return r;
		}
	}
	
	inline void insert(int& rt, const F& v)
	{
		auto res = splitv(rt, v);
		int c = newnode(v);
		rt = merge(merge(res[0], c), res[1]);
	}
	
	inline void assign(int& rt, int pos, const F& v)
	{
		auto res = splitr(rt, pos);
		apply(res[0], v);
		rt = merge(res[0], res[1]);
	}
	
	inline F qsum(int& rt, int pos)
	{
		auto res = splitr(rt, pos);
//		printf("qsum(%lld, %lld)\n", rt, pos);
		F ret = sum[res[0]];
		rt = merge(res[0], res[1]);
		return ret;
	}
	
	void print(int rt)
	{
		if (!rt) return;
		print(ls[rt]), printf("node %lld: sum = %lld/%lld, val = %lld/%lld, tass = %lld/%lld, ls = %lld, rs = %lld\n", rt, sum[rt].i, sum[rt].j, val[rt].i, val[rt].j, tass[rt].i, tass[rt].j, ls[rt], rs[rt]), print(rs[rt]);
	}
}

int 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;
	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;
}

int merge(int& a, int& b)
{
//	printf("merge(%lld, %lld)\n", a, b);
	if (Tree::sz[a] < Tree::sz[b]) swap(a, b);
	if (!b) return a;
	Tree::pushdown(b);
	Tree::insert(a, Tree::val[b]);
	merge(a, Tree::ls[b]), merge(a, Tree::rs[b]);
	return a;
}

int pc;

pair<int, F> getp(int& rt, int a, int b)
{
	// max (y - b) / (x - a)
	int l = 0, r = Tree::sz[rt];
	auto getres = [&](int x)
	{
		F y1 = Tree::qsum(rt, x);
		y1.i -= b * y1.j, y1.j *= (x - a);
//		y1.reduce();
		return y1;
	};
	pc++;
	while (l + 1 < r)
	{
		pc++;
//		int mid1 = (l + r) >> 1, mid2 = mid1 + 1;
		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;
	}
//	printf(")))"), Tree::print(rt);
//	printf("res(l) = (%lld, %lld/%lld), res(r) = (%lld, %lld/%lld)\n", l, getres(l).i, getres(l).j, r, getres(r).i, getres(r).j);
	auto resl = getres(l), resr = getres(r);
	resl.reduce(), resr.reduce();
	if (resl > resr) return {l, resl};
	else return {r, resr};
}

void dfs(int x)
{
//	printf("dfs(%lld)\n", x);
	dp[x] = 0;
	if (son[x].empty()) for (int i = 1; i <= rx[x]; i++) Tree::insert(dp[x], {rs[x], rx[x]});
	else 
	{
		for (int y : son[x]) dfs(y), dp[x] = merge(dp[x], dp[y]);
//		Tree::print(dp[x]);
//		 (-rx[x], -rs[x])
		auto res = getp(dp[x], -rx[x], -rs[x]);
//		printf("proc: res = {%lld, %lld/%lld}\n", res.first, res.second.i, res.second.j);
		int p = res.first;
		F v = res.second;
		Tree::assign(dp[x], p, v);
		for (int i = 1; i <= rx[x]; i++) Tree::insert(dp[x], v);
	}
//	Tree::print(dp[x]);
//	cout << "***";
	auto res = getp(dp[x], -2, -(a[l[x] - 1] + a[r[x] + 1]));
	ans[x] = res.second;
//	printf("%lld: (%lld, %lld/%lld)\n", x, res.first, ans[x].i, ans[x].j);
}

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]);
    Tree::init();
    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 {pc, 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;
//	}
//}