// #include"average.h"
#include<bits/stdc++.h>
#define reg register
#define int long long
const int N=2e5+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];
struct Fac{
    int x,y;
    inline bool operator<(const Fac &A)const{return x*A.y<y*A.x;}
    inline bool operator>(const Fac &A)const{return x*A.y>y*A.x;}
};
std::map<int,Fac> 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) return 0;
    reg int p=l+1,rt=++qwq,lst=0; id[{l,r}]=qwq;
    ID[qwq]={l,r};
    std::cerr<<l<<" "<<r<<" "<<qwq<<"\n";
    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;
}
void split(reg int o,reg int dx,reg int dy,reg int &x,reg int &y){
    if (!o) return x=y=0,void();
    // std::cerr<<o<<"\n"; 
    assert(t[o].ls!=o&&t[o].rs!=o);
    if (dy*t[o].x>=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();
    // std::cerr<<o<<"\n"; 
    assert(t[o].ls!=o&&t[o].rs!=o);
    if (dy*t[o].x>=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+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;
    // std::cerr<<x<<" "<<y<<"\n";
    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){
    // std::cerr<<"<< "<<u<<"\n";
    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]);
        // std::cerr<<"edge "<<u<<" "<<v<<"\n";
        tot=0,dfs(Rt[v]); 
        for (reg int i=1,a,b;i<=tot;i++){
            split(Rt[u],t[nd[i]].x,t[nd[i]].y,a,b);
            // std::cerr<<"qwq "<<t[2].ls<<" "<<t[2].rs<<"\n";
            // std::cerr<<"<<< "<<"\n";
            Rt[u]=merge(merge(a,nd[i]),b);
        }
    }

    tot=0,dfs(Rt[u]); 
    
    sy+=a[ID[u].first]+a[ID[u].second],sx+=2; reg int A,B;
    Split(Rt[u],sx,sy,A,B);
    reg Fac &now=ans[u]; now={sy+t[A].sy,sx+t[A].sx};
    Rt[u]=merge(A,B);

    std::cerr<<"ans "<<now.x<<" "<<now.y<<"\n";

    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);

    std::cerr<<"merge "<<sx<<" "<<sy<<"\n";
}
#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(1,n)); //exit(0);
    // for (reg int i=1;i<=qwq;i++) for (auto j:G[i]) std::cerr<<"edge "<<i<<" "<<j<<"\n";
}
std::array<long long, 2> maximum_average(int i, int j){
    auto [x,y]=ans[id[{i+1,j+1}]]; 
    std::cerr<<"query "<<x<<" "<<y<<"\n";
    // x+=a[i+1]+a[j+1],y+=2;
    reg long long g=std::__gcd(x,y);
    return {x/g,y/g};
}

implementer.cpp: In function ‘void report(std::vector<std::array<int, 2> >)’:
implementer.cpp:31:15: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   31 |     for(auto &[u, v]: tree){
      |               ^
answer.code: In function ‘long long int newnode(long long int, long long int)’:
answer.code:37:71: warning: narrowing conversion of ‘rnd.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()()’ from ‘std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type’ {aka ‘long unsigned int’} to ‘long long int’ [-Wnarrowing]
   37 | inline int newnode(reg int x,reg int y){return t[++idx]={x,y,1,x,y,rnd(),0,0},idx;}
      |                                                                    ~~~^~
answer.code: In function ‘std::array<long long int, 2> maximum_average(int, int)’:
answer.code:106:10: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  106 |     auto [x,y]=ans[id[{i+1,j+1}]];
      |          ^
/usr/bin/ld: /tmp/ccLTfCEg.o: in function `main':
implementer.cpp:(.text.startup+0x109): undefined reference to `construct_two_trees(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status