#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], rx[N], rs[N];
//#define __int128 int
struct F
{
__int128 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 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;
auto d = __gcd(a, b);
return {a / d, b / d};
}
void reduce()
{
auto d = __gcd(i, j);
i /= d, j /= d;
}
}ans[N];
namespace Tree
{
mt19937 rng(20241015);
const int R = 40;
int idx;
signed 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++;
ls[idx] = rs[idx] = 0, sz[idx] = 1, tass[idx] = {0, 1};
val[idx] = sum[idx] = v;
return idx;
}
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]];
}
void apply(int u, F dass)
{
if (!u) return;
sum[u] = {dass.i * sz[u], dass.j}, sum[u].reduce(), val[u] = dass;
tass[u] = dass;
}
void pushdown(int u)
{
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, 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;
}
}
void insert(int& rt, F v)
{
auto res = splitv(rt, v);
int c = newnode(v);
rt = merge(merge(res[0], c), res[1]);
}
void assign(int& rt, int pos, F v)
{
auto res = splitr(rt, pos);
apply(res[0], v);
rt = merge(res[0], res[1]);
}
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(a), Tree::pushdown(b);
Tree::insert(a, Tree::val[b]);
merge(a, Tree::ls[b]), merge(a, Tree::rs[b]);
return a;
}
pair<int, F> getp(int& rt, int a, int b)
{
// max (y - b) / (x - a)
assert(Tree::sz[rt]);
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;
};
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;
}
// 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);
if (getres(l) > getres(r)) return {l, getres(l)};
else return {r, getres(r)};
}
void dfs(int x)
{
// printf("dfs(%lld)\n", x);
dp[x] = 0;
if (son[x].empty())
{
if (rx[x]) for (int i = 1; i <= rx[x]; i++) Tree::insert(dp[x], {rs[x], rx[x]}), assert(Tree::sz[dp[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 {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;
// }
//}