#include "average.h"
#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
using ll = long long;
#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e, v) if (!(e)) { meow("AF@%d\n", __LINE__ ); exit(v); }
#define vc vector
#define eb emplace_back
#define pb push_back
const int N = 300005;
int n, m; ll a[N];
struct frac {
ll a, b;
frac(ll _a = 0, ll _b = 1) : a(_a), b(_b) {}
bool operator < (const frac &rh) const {
return a * rh.b < b * rh.a;
}
bool operator > (const frac &rh) const {
return a * rh.b > b * rh.a;
}
bool operator >= (const frac &rh) const {
return a * rh.b >= b * rh.a;
}
};
using di = pair<ll, ll>; // 差分
#define X first
#define Y second
vc<di> mkv(const vc<di> &l, const vc<di> &r) {
vc<di> f; f.reserve(l.size() + r.size());
int i = 0, j = 0;
for (; i < l.size() && j < r.size(); ) {
if (frac(l[i].Y, l[i].X) > frac(r[j].Y, r[j].X))
f.pb(l[i++]);
else
f.pb(r[j++]);
}
for (; i < l.size(); ++i) f.pb(l[i]);
for (; j < r.size(); ++j) f.pb(r[j]);
return f;
}
// 整体平移，求凸包
void shift(vc<di> &f, ll x, ll y) {
while (f.size() && frac(f[0].Y, f[0].X) >= frac(y, x)) {
y += f[0].Y; x += f[0].X;
f.erase(f.begin());
}
f.emplace(f.begin(), x, y);
}
frac query(vc<di> &f, ll x, ll y) {
frac mn;
ll sx = 0, sy = 0;
U (i, 0, f.size() - 1) {
sx += f[i].X; sy += f[i].Y;
mn = max(mn, frac(sy + y, sx + x));
}
return mn;
}
int L[N * 2], R[N * 2];
map<pair<int, int>, frac> res;
vc<int> g[N * 2];
vc<di> dfs(int u) {
vc<di> F {};
ll sx = -1, sy = -a[R[u]];
for (int v : g[u]) {
vc<di> G = dfs(v);
F = mkv(F, G);
++sx; sy += a[R[v]];
}
if (g[u].empty()) sx = sy = 0;
shift(F, sx, sy);
frac ans = query(F, 2, a[L[u]] + a[R[u]]);
res[{L[u], R[u]}] = ans;
return F;
}
int ch[N][2], ptr;
void dfs0(int u, int l, int r, int p) {
int q = ++ptr;
g[p].pb(q); L[q] = l, R[q] = u;
if (ch[u][0])
dfs0(ch[u][0], l, u, q);
while (ch[u][1] && a[ch[u][1]] == a[u]) {
int v = ch[u][1];
q = ++ptr;
g[p].pb(q); L[q] = u, R[q] = v;
dfs0(ch[v][0], u, v, q);
u = v;
}
q = ++ptr;
g[p].pb(q); L[q] = u, R[q] = r;
if (ch[u][1])
dfs0(ch[u][1], u, r, q);
}
void build() {
int stk[N] {}, sp = 0;
U (i, 1, n) {
while (sp && a[stk[sp]] > a[i])
--sp;
if (sp)
ch[stk[sp]][1] = i;
ch[i][0] = stk[sp + 1];
stk[++sp] = i;
stk[sp + 1] = 0;
}
ptr = 1;
dfs0(stk[1], 0, n + 1, 1);
m = ptr;
// U (i, 1, m) {
// sort(g[i].begin(), g[i].end());
// g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
// meow("[%d,%d]->", L[i], R[i]);
// for (int j : g[i]) {
// meow("[%d,%d] ", L[j], R[j]);
// }
// meow("\n");
// }
}
void initialize(vc<int> A) {
n = A.size();
U (i, 0, n - 1) a[i + 1] = A[i];
build();
dfs(1);
}
array<ll, 2> maximum_average(int i, int j) {
++i; ++j;
auto [x, y] = res[{i, j}];
return {x, y};
}