#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
typedef long double lida;

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

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){
	
	//show2(l,r); show2(nodeNumber, 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);
	}
	
}

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

	for(int v : child[u]){
		dfs(v);
		if(sz(candidates[v]) > sz(candidates[u])) swap(candidates[u], candidates[v]);
		
		for(frac f : candidates[v]){
			candidates[u].insert(f);
		}
		
		lastPoint[u].num += lastPoint[v].num;
		lastPoint[u].denom += lastPoint[v].denom;
	}
	
	frac newPoint = {rangeSum(l+1,r-1), r-l-1};
	
	while(sz(candidates[u]) > 0){
		if(lastPoint[u] < newPoint) break;
		
		auto it = candidates[u].end(); it--;
		
		lastPoint[u].num -= it->num;
		lastPoint[u].denom -= it->denom;
		
		candidates[u].erase(it);
	}

	frac slope = {newPoint.num - lastPoint[u].num, newPoint.denom - lastPoint[u].denom};
	candidates[u].insert(slope);
	lastPoint[u] = newPoint;
	
	///precompute answer here
	if(l == 1 and r == n){
		lint total = rangeSum(l,r);
		lint k = r-l+1;
		
		frac best = {total,k};
		for(frac f : candidates[u]){
			total -= f.num, k -= f.denom;
			
			frac val = {total,k};
			if(best < val) best = val;
		}
		
		precompAns[u] = best;
	}
	
	/*
	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);
}

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