// #include"average.h"
#include<bits/stdc++.h>
#define reg 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;
inline int chk(reg int x,reg int y){return a[x]==a[y]?std::min(x,y):a[x]<a[y]?x:y;}
inline int qry(reg int l,reg int r){reg int L=std::__lg(r-l+1); return chk(st[L][l],st[L][r-(1<<L)+1]);}
int build(reg int l,reg int r){
    if (r==l+1){
        ++qwq,id[ID[qwq]={l,r}]=qwq;
        ans[qwq]={a[l]+a[r],2};
        return 0;
    }
    reg int p=l+1,rt=++qwq,lst=0; id[{l,r}]=qwq;
    ID[qwq]={l,r};
    vc[rt].push_back(l); 
    while (p<r){
        reg 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 (reg int i=0;i+1<vc[rt].size();i++){
        reg int v=build(vc[rt][i],vc[rt][i+1]);
        if (v) G[rt].push_back(v);
    }
    return rt;
}
inline int newnode(reg int x,reg int y){return t[++idx]={x,y,1,x,y,rnd(),0,0},idx;}
inline void pushup(reg 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(reg int o,reg int dx,reg int dy,reg int &x,reg 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(reg int o,reg int dx,reg int dy,reg int &x,reg 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(reg int x,reg 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(reg int o){if (!o) return; dfs(t[o].ls),nd[++tot]=o,dfs(t[o].rs);}
void Dfs(reg int u){
    reg int sx=0,sy=0;
    for (reg 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 (reg int i=1,a,b;i<=tot;i++){
            t[nd[i]].ls=t[nd[i]].rs=0,t[nd[i]].sx=t[nd[i]].x,t[nd[i]].sy=t[nd[i]].y,t[nd[i]].sz=1;
            split(Rt[u],t[nd[i]].x,t[nd[i]].y,a,b);
            Rt[u]=merge(merge(a,nd[i]),b);
        }
    }
    sy+=a[ID[u].first]+a[ID[u].second],sx+=2; reg int A,B;
    Split(Rt[u],sx,sy,A,B);
    ans[u]={sy+t[A].sy,sx+t[A].sx};
    Rt[u]=merge(A,B);
    sy-=a[ID[u].first]+a[ID[u].second],sx-=2;
    Split(Rt[u],sx,sy,A,B);
    sx+=t[A].sx,sy+=t[A].sy;
    Rt[u]=merge(newnode(sx,sy),B);
}
#undef int
void initialize(std::vector<int> A){
    n=A.size(); for (reg int i=1;i<=n;i++) a[i]=A[i-1],st[0][i]=i;
    for (reg int j=1;1<<j<=n;j++) for (reg 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};
}