// #include"average.h"
#include<bits/stdc++.h>
#define register
#define int long long
const int N=6e5+10;
int n,a[N],st[20][N],idx,m,rt[N];
std::mt19937 rnd(233);
std::vector<int> vc[N],G[N];
std::pair<int,int> ID[N];
int ls[N],rs[N],sx[N],sy[N],X[N],Y[N],val[N],sz[N];
std::map<std::pair<int,int>,std::array<int,2>> ans;
int chk(int x,int y){return a[x]==a[y]?std::min(x,y):a[x]<a[y]?x:y;}
int qry(int l,int r){int L=std::__lg(r-l+1); return chk(st[L][l],st[L][r-(1<<L)+1]);}
int build(int l,int r){
    if (r==l+1) return ans[ID[++m]={l,r}]={a[l]+a[r],2},0;
    int p=l+1,u=++m,now,v;
    ID[m]={l,r},vc[u].push_back(l); 
    while (p<r){
        now=qry(p,r-1); if (p-1!=l&&a[now]!=a[p-1]) break;
        vc[u].push_back(now),p=now+1;
    }
    vc[u].push_back(r),p=0;
    for (auto x:vc[u]){if (p) v=build(p,x),v?G[u].push_back(v):void();p=x;}
    return u;
}
int nwnd(int x,int y){int o=++idx; return X[o]=sx[o]=x,Y[o]=sy[o]=y,sz[o]=1,val[o]=rnd(),o;}
void up(int o){sx[o]=sx[ls[o]]+X[o]+sx[rs[o]],sy[o]=sy[ls[o]]+Y[o]+sy[rs[o]],sz[o]=sz[ls[o]]+1+sz[rs[o]];}
#define ll __int128
void spt(int o,int dx,int dy,int &x,int &y){
    if (!o) return x=y=0,void();
    if ((ll)dy*X[o]>=(ll)Y[o]*dx) y=o,spt(ls[o],dx,dy,x,ls[y]),up(y);
    else x=o,spt(rs[o],dx,dy,rs[x],y),up(x);
}
void Spt(int o,int dx,int dy,int &x,int &y){
    if (!o) return x=y=0,void();
    if ((ll)(dy+sy[ls[o]])*X[o]>=(ll)Y[o]*(dx+sx[ls[o]])) y=o,Spt(ls[o],dx,dy,x,ls[y]),up(y);
    else x=o,Spt(rs[o],dx+sx[ls[o]]+X[o],dy+sy[ls[o]]+Y[o],rs[x],y),up(x);
}
int mge(int x,int y){
    if (!x||!y) return x+y;
    if (val[x]>val[y]) return rs[x]=mge(rs[x],y),up(x),x;
    return ls[y]=mge(x,ls[y]),up(y),y;
}
int nd[N],tot;
void dfs(int o){if (o) dfs(ls[o]),nd[++tot]=o,dfs(rs[o]);}
void Dfs(int u){
    int Sx=0,Sy=0,A,B; auto [l,r]=ID[u];
    for (auto x:vc[u]) if (x!=l&&x!=r) Sx++,Sy+=a[x];
    for (auto v:G[u]){
        Dfs(v);  
        if (sz[rt[u]]<sz[rt[v]]) std::swap(rt[u],rt[v]);
        tot=0,dfs(rt[v]); 
        for (int i=1,x;x=nd[i],i<=tot;i++)
            ls[x]=rs[x]=0,sx[x]=X[x],sy[x]=Y[x],sz[x]=1,
            spt(rt[u],X[x],Y[x],A,B),rt[u]=mge(mge(A,x),B);
    }
    Spt(rt[u],Sx+2,Sy+a[l]+a[r],A,B),
    ans[{l,r}]={Sy+sy[A]+a[l]+a[r],Sx+sx[A]+2},rt[u]=mge(A,B),
    Spt(rt[u],Sx,Sy,A,B),rt[u]=mge(nwnd(Sx+sx[A],Sy+sy[A]),B);
}
#undef int
void initialize(std::vector<int> A){
    n=A.size(); for (int i=1;i<=n;i++) a[i]=A[i-1],st[0][i]=i;
    for (int j=1;1<<j<=n;j++) for (int i=1;i+(1<<j)-1<=n;i++) st[j][i]=chk(st[j-1][i],st[j-1][i+(1<<j-1)]);
    Dfs(build(0,n+1)); 
}
std::array<long long,2>maximum_average(int i, int j){return ans[{i+1,j+1}];}