#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

int pc;
__int128 gcd(__int128 a, __int128 b)
{
    if (a == 0) return b;
    if (b == 0) return a;

    int az = __builtin_ctzll(a & 0xffffffffffffffff);
    int bz = __builtin_ctzll(b & 0xffffffffffffffff);
    int shift = min(az, bz);
    b >>= bz;
    
    while (a != 0) {
        a >>= az;
        __int128 diff = b - a;
        az = __builtin_ctzll(diff & 0xffffffffffffffff);
        b = min(a, b);
        a = abs(diff);
    }
    
    return b << shift;
}

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
	{
		return {i * f2.j + j * f2.i, j * f2.j};
	}
	
}ans[N];

struct V
{
	__int128 x, y;
	
	V operator+ (const V& v2) const
	{
		return {x + v2.x, y + v2.y};
	}
	
	bool operator< (const V& v2) const
	{
		return y * v2.x < x * v2.y;
	}
	
	bool operator> (const V& v2) const
	{
		return y * v2.x > x * v2.y;
	}
};

mt19937 rng(20241015);
namespace Tree
{
	const int R = 2;
	int idx;
	int ls[N * R], rs[N * R], sz[N * R];
	V val[N * R], sum[N * R];
	
	void init()
	{
		val[0] = sum[0] = {0, 0};
	}
	
	int newnode(V v)
	{
		idx++;
		assert(idx < N * R);
		ls[idx] = rs[idx] = 0, sz[idx] = 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}, 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};
		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 V& v)
	{
		// [1, v] [v, inf)
		if (!u) return {0, 0};
		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;
		
		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 V& 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, ls = %lld, rs = %lld\n", rt, sum[rt].y, sum[rt].x, val[rt].y, val[rt].x, ls[rt], rs[rt]), print(rs[rt]);
 	}

	void pop(int& rt)
	{
		auto res = splitr(rt, 1);
		rt = res[1];
	}
	
	V front(int& rt)
	{
		auto res = splitr(rt, 1);
		V ret = val[res[0]];
		rt = merge(res[0], res[1]);
		return ret;
	}
}

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;
	merge(a, Tree::ls[b]), merge(a, Tree::rs[b]);
	Tree::ls[b] = Tree::rs[b] = 0, Tree::sz[b] = 1, Tree::sum[b] = Tree::val[b];
	auto res = Tree::splitv(a, Tree::val[b]);
	a = Tree::merge(Tree::merge(res[0], b), res[1]);
}

void getp(int rt, int a, int b, V cur, int rk, V& ans)
{
//	printf("getp(%lld, %lld, %lld, {%lld, %lld}, %lld)\n", rt, a, b, cur.i, cur.j, rk);
    if (!rt) return;
    V f = cur + Tree::sum[Tree::ls[rt]], d = Tree::val[rt];
    f.y -= b, f.x -= 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
    {
        ans = cur + Tree::sum[Tree::ls[rt]] + Tree::val[rt];
        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()) Tree::insert(dp[x], {rx[x], rs[x]});
	else 
	{
		for (int y : son[x]) 
		{
			dfs(y);
			if (Tree::sz[dp[x]] < Tree::sz[dp[y]]) swap(dp[x], dp[y]);
			merge(dp[x], dp[y]);
		}
		if (x == 1) return;
//		Tree::print(dp[x]);
//		 (-rx[x], -rs[x])
//printf("getp(%lld)\n", x);
		V res = {0, 0};
		getp(dp[x], -rx[x], -rs[x], {0, 0}, 0, res);
//		printf("proc: res = {%lld, %lld}\n", res.y, res.x);
		while (!(Tree::front(dp[x]) < res)) Tree::pop(dp[x]);
		res.x += rx[x], res.y += rs[x];
		Tree::insert(dp[x], res);
//		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);
	V res = {0, 0};
	getp(dp[x], -2, -(a[l[x] - 1] + a[r[x] + 1]), {0, 0}, 0, res);
	res.x += 2, res.y += (a[l[x] - 1] + a[r[x] + 1]);
	ans[x] = {res.y, res.x};
//	printf("%lld: (%lld, %lld)\n", x, 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(rng() % 20 + 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';
// 	}
// }

answer.code: In function ‘__int128 gcd(__int128, __int128)’:
answer.code:29:16: error: call of overloaded ‘abs(__int128&)’ is ambiguous
   29 |         a = abs(diff);
      |             ~~~^~~~~~
In file included from /usr/include/c++/13/cstdlib:79,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:42,
                 from answer.code:1:
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/13/cstdlib:81:
/usr/include/c++/13/bits/std_abs.h:130:3: note: candidate: ‘constexpr __gnu_cxx::__bfloat16_t std::abs(__gnu_cxx::__bfloat16_t)’
  130 |   abs(__gnu_cxx::__bfloat16_t __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:124:3: note: candidate: ‘constexpr _Float128 std::abs(_Float128)’
  124 |   abs(_Float128 __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:114:3: note: candidate: ‘constexpr _Float64 std::abs(_Float64)’
  114 |   abs(_Float64 __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:108:3: note: candidate: ‘constexpr _Float32 std::abs(_Float32)’
  108 |   abs(_Float32 __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:102:3: note: candidate: ‘constexpr _Float16 std::abs(_Float16)’
  102 |   abs(_Float16 __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code: In function ‘void Tree::print(long long int)’:
answer.code:238:60: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 3 has type ‘__int128’ [-Wformat=]
  238 |                 print(ls[rt]), printf("node %lld: sum = %lld/%lld, val = %lld/%lld, ls = %lld, rs = %lld\n", rt, sum[rt].y, sum[rt].x, val[rt].y, val[rt].x, ls[rt], rs[rt]), print(rs[rt]);
      |                                                         ~~~^                                                     ~~~~~~~~~
      |                                                            |                                                             |
      |                                                            long long int                                                 __int128
answer.code:238:65: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 4 has type ‘__int128’ [-Wformat=]
  238 |                 print(ls[rt]), printf("node %lld: sum = %lld/%lld, val = %lld/%lld, ls = %lld, rs = %lld\n", rt, sum[rt].y, sum[rt].x, val[rt].y, val[rt].x, ls[rt], rs[rt]), print(rs[rt]);
      |                                                              ~~~^                                                           ~~~~~~~~~
      |                                                                 |                                                                   |
      |                                                                 long long int                                                       __int128
answer.code:238:77: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 5 has type ‘__int128’ [-Wformat=]
  238 |                 print(ls[rt]), printf("node %lld: sum = %lld/%lld, val = %lld/%lld, ls = %lld, rs = %lld\n", rt, sum[rt].y, sum[rt].x, val[rt].y, val[rt].x, ls[rt], rs[rt]), print(rs[rt]);
      |                                                                          ~~~^                                                          ~~~~~~~~~
      |                                                                             |                                                                  |
      |                                                                             long long int                                                      __int128
answer.code:238:82: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 6 has type ‘__int128’ [-Wformat=]
  238 |                 print(ls[rt]), printf("node %lld: sum = %lld/%lld, val = %lld/%lld, ls = %lld, rs = %lld\n", rt, sum[rt].y, sum[rt].x, val[rt].y, val[rt].x, ls[rt], rs[rt]), print(rs[rt]);
      |                                                                               ~~~^                                                                ~~~~~~~~~
      |                                                                          ...