#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;
}
int merge(int a, int b)
{
if (!b) return;
Tree::insert(a, Tree::val[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);
dp[x] = 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';
// }
//}