// #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::map<std::pair<int,int>,int> id;
std::pair<int,int> ID[N];
struct Node{int x,y,sz,sx,sy,val,ls,rs;}t[N];
std::map<int,std::pair<int,int>> 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){
        ++qwq,id[ID[qwq]={l,r}]=qwq;
        ans[qwq]={a[l]+a[r],2};
        return 0;
    }
    int p=l+1,rt=++qwq,lst=0; id[{l,r}]=qwq;
    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){return t[++idx]={x,y,1,x,y,rnd(),0,0},idx;}
void pushup(int o){
    t[o].sx=t[t[o].ls].sx+t[o].x+t[t[o].rs].sx,
    t[o].sy=t[t[o].ls].sy+t[o].y+t[t[o].rs].sy,
    t[o].sz=t[t[o].ls].sz+1+t[t[o].rs].sz;
}
#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*t[o].x>=(ll)t[o].y*dx) y=o,split(t[o].ls,dx,dy,x,t[y].ls),pushup(y);
    else x=o,split(t[o].rs,dx,dy,t[x].rs,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+t[t[o].ls].sy)*t[o].x>=(ll)t[o].y*(dx+t[t[o].ls].sx)) y=o,Split(t[o].ls,dx,dy,x,t[y].ls),pushup(y);
    else x=o,Split(t[o].rs,dx+t[t[o].ls].sx+t[o].x,dy+t[t[o].ls].sy+t[o].y,t[x].rs,y),pushup(x);
}
int merge(int x,int y){
    if (!x||!y) return x+y;
    if (t[x].val>t[y].val) return t[x].rs=merge(t[x].rs,y),pushup(x),x;
    return t[y].ls=merge(x,t[y].ls),pushup(y),y;
}
int nd[N],tot;
void dfs(int o){if (!o) return; dfs(t[o].ls),nd[++tot]=o,dfs(t[o].rs);}
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 (t[Rt[u]].sz<t[Rt[v]].sz) std::swap(Rt[u],Rt[v]);
        tot=0,dfs(Rt[v]); 
        for (int i=1,a,b,x;x=nd[i],i<=tot;i++){
            t[x].ls=t[x].rs=0,t[x].sx=t[x].x,t[x].sy=t[x].y,t[x].sz=1;
            split(Rt[u],t[x].x,t[x].y,A,B);
            Rt[u]=merge(merge(A,x),B);
        }
    }
    Split(Rt[u],sx+a[l]+a[r],sy+2,A,B);
    ans[u]={sy+t[A].sy+a[l]+a[r],sx+t[A].sx+2},Rt[u]=merge(A,B);
    Split(Rt[u],sx,sy,A,B),Rt[u]=merge(newnode(sx+t[A].sx,sy+t[A].sy),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){
    auto [x,y]=ans[id[{i+1,j+1}]]; 
    return {x,y};
}