#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)
	{
		i = a, j = b;
		__int128 d = __gcd(i, j);
		i /= d, j /= 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};
	}
	
}ans[N];

int pc;
mt19937 rng(20241015);
namespace Tree
{
	const int R = 20;
	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;
	    pc++;
		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}, val[u] = dass;
		tass[u] = dass;
	}
	
	inline void pushdown(int u)
	{
		if (!u) return;
		if (tass[u].i == 0) return;
	    pc++;
		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)
	{
	    if (!rt) return {0, 1};
	    pushdown(rt);
	    if (pos <= sz[ls[rt]]) return qsum(ls[rt], pos);
	    else return sum[ls[rt]] + val[rt] + qsum(rs[rt], pos - sz[ls[rt]] - 1);
// 		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;
	}
	
	const F& kth(int rt, int k)
	{
	    int p = sz[ls[rt]];
	    pushdown(rt);
	    if (k <= p) return kth(ls[rt], k);
	    else if (k > p + 1) return kth(rs[rt], k - sz[ls[rt]] - 1);
	    else return val[rt];
// 		auto res = splitr(rt, k);
// 		auto res2 = splitr(res[0], k - 1);
// 		F ret = val[res2[1]];
// 		rt = merge(merge(res2[0], res2[1]), 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 pc2;
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;
}

void merge(int& a, int b)
{
	if (!b) return;
	Tree::insert(a, Tree::val[b]);
	Tree::pushdown(b);
	merge(a, Tree::ls[b]), merge(a, Tree::rs[b]);
}

void getp(int rt, int a, int b, F cur, int rk, pair<int, F>& ans)
{
//	printf("getp(%lld, %lld, %lld, {%lld, %lld}, %lld)\n", rt, a, b, cur.i, cur.j, rk);
    if (!rt) return;
    Tree::pushdown(rt);
    F f = cur + Tree::sum[Tree::ls[rt]], d = Tree::val[rt];
    f.i -= b * f.j, f.j *= (rk + Tree::sz[Tree::ls[rt]] - a);
//    printf("f\' = {%lld, %lld}, d = {%lld, %lld}\n", f.i, f.j, d.i, d.j);
    if (f > d) getp(Tree::ls[rt], a, b, cur, rk, ans);
    else
    {
    	f = cur + Tree::sum[Tree::ls[rt]] + Tree::val[rt];
    	f.i -= b * f.j, f.j *= (rk + Tree::sz[Tree::ls[rt]] + 1 - a);
        ans = {rk + Tree::sz[Tree::ls[rt]] + 1, f};
        getp(Tree::rs[rt], a, b, cur + Tree::sum[Tree::ls[rt]] + Tree::val[rt], rk + Tree::sz[Tree::ls[rt]] + 1, ans);
    }
}

// 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;
// 	};
// 	int dpc = 0;
// 	while (l < r)
// 	{
// //		int mid1 = (l + r) >> 1, mid2 = mid1 + 1;
//         dpc += 2;
// 		int mid = (l + r) >> 1;
// 		F f = Tree::qsum(rt, mid), d = Tree::kth(rt, mid + 1);
// 		f.i -= b * f.j, f.j *= (mid - a);
// 		if (f > d) r = mid;
// 		else l = mid + 1;
// 	}
// //	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);
// 	dpc++;
// 	assert(dpc < 19 * 2 + 1);
// 	pc2 += dpc;
// 	auto resl = getres(l);
// 	return {l, resl};
// }

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);
			if (Tree::sz[dp[x]] < Tree::sz[dp[y]]) swap(x, y);
			merge(dp[x], dp[y]);
		}
		if (x == 1) return;
//		Tree::print(dp[x]);
//		 (-rx[x], -rs[x])
//printf("getp(%lld)\n", x);
		pair<int, F> res = {0, {rx[x], rs[x]}};
		getp(dp[x], -rx[x], -rs[x], {0, 1}, 0, res);
//		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 << "***";
	assert(pc < 3.5e7);
	pair<int, F> res = {0, {2, a[l[x] - 1] + a[r[x] + 1]}};
	getp(dp[x], -2, -(a[l[x] - 1] + a[r[x] + 1]), {0, 1}, 0, res);
	ans[x] = res.second;
//	printf("%lld: (%lld, %lld/%lld)\n", x, res.first, ans[x].i, ans[x].j);
}

bool flag;

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();
    if (!flag) 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}];
	if (flag) return {idx, ans[id].j};
	return {ans[id].i, ans[id].j};
}

//signed main()
//{
//	cin.tie(0)->sync_with_stdio(0);
//	
//	int n; cin >> n;
//	vector<signed> A;
// 	for (int i = 1, ai; i <= n; i++) cin >> ai, A.push_back(ai); 
////	for (int i = 1, ai; i <= n; i++) A.push_back(min(i, n - i + 1));
//	initialize(A);
//	printf("idx = %lld, pc = %lld, pc2 = %lld, time = %lld\n", idx, pc, pc2, (int)clock());
//	int l, r;
//	while (cin >> l >> r)
//	{
//		auto res = maximum_average(l, r);
//		cout << res[0] << ' ' << res[1] << '\n';
//	}
//}