#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define showlist(x) cerr << #x << " is "; for(auto p : x) cerr << p << " "; cerr << endl;
typedef long long lint;
typedef pair<lint,lint> ii;
#define num first
#define denom second

const lint inf = 1e15;
int n;
lint arr[300005];
lint psum[300005];

map<ii, int> nodeRanges;
int nodeNumber = 0;
vector<int> child[600006];

int L[600006];
int R[600006];

struct frac{
	lint num = 0, denom = 0;
	bool operator < (const frac &f) const {
		if(f.num == 0) return false;
		if(num == 0) return true; 
		return num*f.denom < f.num*denom;
	};
};
frac lastPoint[600006];
multiset<frac> candidates[600006];
map<frac, int> discretizeFracs;

frac precompAns[600006];

const int N = 300003;
ii rangemin[600015];
void pointminupdate(int i, lint x){
	rangemin[i+N] = ii(x,i); 
	for(i = (i+N)/2;i;i >>= 1) rangemin[i] = min(rangemin[i<<1], rangemin[i<<1|1]);
}
ii rangeminquery(int l, int r){
	ii res = {inf,inf};
	for(l += N,r += N+1;l < r;l >>= 1, r >>= 1){
		if(l&1) res = min(res, rangemin[l++]);
		if(r&1) res = min(res, rangemin[--r]);
	}
	return res;
}


lint rangeSum(int l, int r){
	return psum[r] - psum[l-1];
}

void recurse(int l, int r, int parent){
	
	L[nodeNumber] = l;
	R[nodeNumber] = r;
	int thisNodeNumber = nodeNumber;
	nodeRanges[ii(l,r)] = thisNodeNumber; 
	if(parent != -1) child[parent].push_back(thisNodeNumber);
	nodeNumber++;
	
	
	lint minVal = rangeminquery(l+1,r-1).first;
	if(minVal >= inf/2) return;
		
	vector<int> pos = {l};
	
	while(true){
		ii minValPos = rangeminquery(l+1,r-1);
		if(minValPos.first != minVal) break;
		
		int p = minValPos.second;
		pointminupdate(p, inf);
		pos.push_back(p);
	}
	
	pos.push_back(r);
	
	//showlist(pos);
	
	for(int i = 1;i < sz(pos);i++){
		recurse(pos[i-1], pos[i], thisNodeNumber);
	}
	
}

///step 1, discretize all segments
///step 2, do the thing
struct node{
	int s, e, m;
	node *l = nullptr, *r = nullptr;
	frac val = {0,0};
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
	}
	
	void create(){
		if(s == e) return;
		if(l != nullptr) return;
		l = new node(s,m);
		r = new node(m+1,e);
	}
	
	void update(int X, lint NUM, lint DENOM){
		create();
		val.num += NUM, val.denom += DENOM;
		if(s != e){
			if(X <= m) l->update(X, NUM, DENOM);
			else r->update(X, NUM, DENOM);
		}
	}
	
	frac findBest(frac base){
		create();	
		if(s == e) return base;
		
		frac midpoint = {base.num - l->val.num, base.denom - l->val.denom};
		
		//show2(base.num, base.denom);
		//show2(l->val.num, l->val.denom);
		
		
		if(base < midpoint) return r->findBest(midpoint);
		else return l->findBest(base);
	}
	
} *root[10006];

int run = 1;
void addSlope(int u, frac f){
	candidates[u].insert(f);
	if(run == 1) discretizeFracs[f] = -1;
	if(run == 2){
		//assert(discretizeFracs[f] != 0);
		root[u]->update(discretizeFracs[f], f.num, f.denom);
	}
}
void removeSlope(int u, frac f){
	candidates[u].erase(candidates[u].find(f));
	if(run == 2){
		//assert(discretizeFracs[f] != 0);
		root[u]->update(discretizeFracs[f], -f.num, -f.denom);
	}
}

void dfs(int u){
	int r = R[u], l = L[u];
	
	if(sz(child[u]) == 0){
		precompAns[u] = {arr[l] + arr[r], 2};
		lastPoint[u] = {0,0};
		return;
	}

	for(int v : child[u]){
		dfs(v);
		if(sz(candidates[v]) > sz(candidates[u])){
			swap(candidates[u], candidates[v]);
			swap(root[u], root[v]);
		}
		
		for(frac f : candidates[v]) addSlope(u, f);

		lastPoint[u].num += lastPoint[v].num;
		lastPoint[u].denom += lastPoint[v].denom;
	}
	
	frac slope = {rangeSum(l+1,r-1) - lastPoint[u].num, r-l-1 - lastPoint[u].denom};
	
	while(sz(candidates[u]) > 0){
		auto it = candidates[u].end(); it--;
		
		if(slope < *it){
			slope.num += it->num;
			slope.denom += it->denom;
			removeSlope(u, *it);
		}
		else break;
	}
	
	addSlope(u, slope);
	lastPoint[u] = {rangeSum(l+1,r-1), r-l-1};
	
	if(run == 2){
		lint total = rangeSum(l,r);
		lint k = r-l+1;
		precompAns[u] = root[u]->findBest({total,k});
	}
	
	/*
	show2(l,r);
	for(frac f : candidates[u]) show2(f.num, f.denom);
	cerr << endl;
	//*/
}

void initialize(std::vector<int> A){

	n = (int)(A.size());
	for(int i = 1;i <= n;i++) arr[i] = A[i-1];
	for(int i = 1;i <= n+1;i++) psum[i] = arr[i] + psum[i-1];	
	for(int i = 0;i <= n+1;i++) pointminupdate(i, arr[i]);

	recurse(0,n+1,-1);
	dfs(0);
	
	int discCounter = 1;
	for(auto &it : discretizeFracs){
		//show2(it.first.num, it.first.denom);
		it.second = discCounter++;
	}
	
	show("RUN 2");
	for(int i = 0;i <= nodeNumber;i++){
		candidates[i].clear();
		lastPoint[i] = {0,0};
		root[i] = new node(0,sz(discretizeFracs));
	}
	run = 2;
	
	dfs(0);
}

std::array<long long, 2> maximum_average(int l, int r){
    l++, r++;
    
    frac res = precompAns[nodeRanges[ii(l,r)]];
    
    return {res.num, res.denom};
}