// #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,qwq,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){
        ID[++qwq]={l,r};
        ans[{l,r}]={a[l]+a[r],2};
        return 0;
    }
    int p=l+1,rt=++qwq,lst=0;
    ID[qwq]={l,r},vc[rt].push_back(l); 
    while (p<r){
        int now=qry(p,r-1); if (lst&&a[now]!=a[lst]) break;
        vc[rt].push_back(lst=now),p=lst+1;
    }
    vc[rt].push_back(r);
    for (int i=0;i+1<vc[rt].size();i++){
        int v=build(vc[rt][i],vc[rt][i+1]);
        if (v) G[rt].push_back(v);
    }
    return rt;
}
int newnode(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 pushup(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 split(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,split(ls[o],dx,dy,x,ls[y]),pushup(y);
    else x=o,split(rs[o],dx,dy,rs[x],y),pushup(x);
}
void Split(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,Split(ls[o],dx,dy,x,ls[y]),pushup(y);
    else x=o,Split(rs[o],dx+sx[ls[o]]+X[o],dy+sy[ls[o]]+Y[o],rs[x],y),pushup(x);
}
int merge(int x,int y){
    if (!x||!y) return x+y;
    if (val[x]>val[y]) return rs[x]=merge(rs[x],y),pushup(x),x;
    return ls[y]=merge(x,ls[y]),pushup(y),y;
}
int nd[N],tot;
void dfs(int o){if (!o) return; 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 (int i=1;i+1<vc[u].size();i++) Sx++,Sy+=a[vc[u][i]];
    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,a,b,x;x=nd[i],i<=tot;i++){
            ls[x]=rs[x]=0,sx[x]=X[x],sy[x]=Y[x],sz[x]=1;
            split(Rt[u],X[x],Y[x],A,B);
            Rt[u]=merge(merge(A,x),B);
        }
    }
    Split(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]=merge(A,B);
    Split(Rt[u],Sx,Sy,A,B),Rt[u]=merge(newnode(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}];}