#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<array>
#include"average.h"
#define N 600004
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
long long gcd(long long x,long long y)
{
if (!y) return x;
return gcd(y,x%y);
}
struct rds
{
int num,data;
bool operator < (const rds &t)const
{
return data!=t.data?data<t.data:num<t.num;
}
};
rds ST[N+1][21];
struct frac
{
long long x;
int y;
bool operator < (const frac &t)const
{
return (__int128)(x)*t.y<(__int128)(y)*t.x;
}
bool operator > (const frac &t)const
{
return (__int128)(x)*t.y>(__int128)(y)*t.x;
}
bool operator != (const frac &t)const
{
return (__int128)(x)*t.y!=(__int128)(y)*t.x;
}
};
frac zero,delta[N+1],delta2[N+1],dp[N+1],tong[N+1];
frac operator + (frac a,frac b)
{
return (frac){a.x+b.x,a.y+b.y};
}
frac operator - (frac a,frac b)
{
return (frac){a.x-b.x,a.y-b.y};
}
struct reads
{
int num;
frac data;
bool operator < (const reads &t)const
{
return data<t.data;
}
};
priority_queue<reads>sq;
vector<int>E[N+1];
vector<reads>v[N+1];
int n,length,leng,nt[N+1],nt2[N+1],a[N+1],lg[N+1],fa[N+1],srt[N+1],rt[N+1];
bool used[N+1];
rds get_minn(int l,int r)
{
int lw=lg[r-l+1];
return min(ST[l][lw],ST[r-(1<<lw)+1][lw]);
}
int solve(int l,int r)
{
int nw=++length;
if (a[l]>=a[r]) nt[l]=nw;
else nt2[r]=nw;
if (l+1==r)
{
delta[nw]=(frac){0,0},delta2[nw]=(frac){a[l]+a[r],2};
return nw;
}
rds d=get_minn(l+1,r-1),ds;
int ps=l+1,dt;
vector<int>p;
p.push_back(l);
while (ps<=r-1)
{
ds=get_minn(ps,r-1);
if (ds.data==d.data) p.push_back(ds.num),ps=ds.num+1;
else break;
}
p.push_back(r),delta[nw]=(frac){1ll*d.data*(p.size()-2),p.size()-2},delta2[nw]=(frac){1ll*d.data*(p.size()-2)+a[l]+a[r],p.size()};
for (int i=0;i+1<p.size();++i) dt=solve(p[i],p[i+1]),E[nw].push_back(dt),fa[dt]=nw;
return nw;
}
struct seg
{
struct node
{
int ls,rs;
frac data;
};
node tree[40*N+1];
int lengths;
void push_up(int k)
{
tree[k].data=tree[tree[k].ls].data+tree[tree[k].rs].data;
return;
}
int merge(int x,int y,int L,int R)
{
if (!x||!y) return x^y;
if (L==R)
{
tree[x].data=tree[x].data+tree[y].data;
return x;
}
int mid=(L+R)>>1;
tree[x].ls=merge(tree[x].ls,tree[y].ls,L,mid),tree[x].rs=merge(tree[x].rs,tree[y].rs,mid+1,R),push_up(x);
return x;
}
void add(int &k,int L,int R,int x,frac d)
{
if (!k) k=++lengths;
if (L==R)
{
tree[k].data=tree[k].data+d;
return;
}
int mid=(L+R)>>1;
if (x<=mid) add(tree[k].ls,L,mid,x,d);
else add(tree[k].rs,mid+1,R,x,d);
push_up(k);
return;
}
frac calc(int k,int L,int R,frac d)
{
if (!k) return d;
if (L==R)
{
if (d<tong[L]) return d+tree[k].data;
else return d;
}
int mid=(L+R)>>1;
if ((d+tree[tree[k].ls].data)<tong[mid+1]) return calc(tree[k].rs,mid+1,R,d+tree[tree[k].ls].data);
else return calc(tree[k].ls,L,mid,d);
}
};
seg T;
int find(int x)
{
if (rt[x]==x) return x;
return rt[x]=find(rt[x]);
}
void unionn(int x,int y)
{
v[fa[x]].push_back((reads){leng,delta[x]});
if (y!=1) v[fa[y]].push_back((reads){leng,zero-delta[x]});
delta[y]=delta[y]+delta[x],sq.push((reads){y,delta[y]}),rt[x]=y;
return;
}
void dfs(int x)
{
for (int i=0;i<E[x].size();++i) dfs(E[x][i]),srt[x]=T.merge(srt[x],srt[E[x][i]],1,leng);
for (int i=0;i<v[x].size();++i) T.add(srt[x],1,leng,v[x][i].num,v[x][i].data);
dp[x]=T.calc(srt[x],1,leng,delta2[x]);
return;
}
array<long long,2>calc(frac d)
{
int g=gcd(d.x,d.y);
d.x/=g,d.y/=g;
return {d.x,d.y};
}
void initialize(vector<int>A)
{
reads top;
for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
n=A.size();
for (int i=1;i<=n;++i) a[i]=A[i-1],ST[i][0]=(rds){i,a[i]};
for (int i=1;i<=lg[n];++i)
for (int j=1;j+(1<<i)-1<=n;++j)
ST[j][i]=min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
solve(0,n+1);
for (int i=1;i<=length;++i)
{
rt[i]=i;
if (!E[i].empty()) sq.push((reads){i,delta[i]});
}
while (!sq.empty())
{
top=sq.top(),sq.pop();
if (used[top.num]) continue;
used[top.num]=1;
if (top.num!=1) tong[++leng]=top.data,unionn(top.num,find(fa[top.num]));
}
dfs(1);
return;
}
array<long long,2>maximum_average(int l,int r)
{
l++,r++;
return calc(dp[a[l]>=a[r]?nt[l]:nt2[r]]);
}