// MagicDark
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define debug cerr << "\033[32m[" << __LINE__ << "]\033[0m "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
const int N = 3e5 + 10;
int n, m, a[N], id[N], tot, l[N], r[N];
ll s[N];
map <int, vector <int>> mp;
vector <int> v[N], e[N];
ll gcd(ll x, ll y) {return y ? gcd(y, x % y) : x;}
struct frac {// x / y
	ll x, y;
	frac(ll xx = 0, ll yy = 1) {
		x = xx, y = yy;
		ll k = gcd(x, y);
		x /= k, y /= k;
	}
};
frac operator + (frac x, frac y) {
	return (frac) {x.x * y.y + x.y * y.x, x.y * y.y};
}
frac operator - (frac x, frac y) {
	return (frac) {x.x * y.y - x.y * y.x, x.y * y.y};
}
frac operator / (frac x, frac y) {
	return (frac) {x.x * y.y, x.y * y.x};
}
frac operator * (frac x, frac y) {
	return (frac) {x.x * y.x, x.y * y.y};
}
bool operator < (frac x, frac y) {
	return (__int128) x.x * y.y < (__int128) y.x * x.y;
}
bool operator == (frac x, frac y) {
	return (__int128) x.x * y.y == (__int128) y.x * x.y;
}
bool operator <= (frac x, frac y) {
	return (__int128) x.x * y.y <= (__int128) y.x * x.y;
}
bool operator > (frac x, frac y) {
	return (__int128) x.x * y.y > (__int128) y.x * x.y;
}
bool operator >= (frac x, frac y) {
	return (__int128) x.x * y.y >= (__int128) y.x * x.y;
}
frac ans[N];
struct vec {
	ll x, y;
	vec(ll xx = 0, ll yy = 0) { x = xx, y = yy; }
};
vec operator + (vec x, vec y) {
	return (vec) {x.x + y.x, x.y + y.y};
}
vec operator - (vec x, vec y) {
	return (vec) {x.x - y.x, x.y - y.y};
}
vec& operator += (vec& x, vec y) {
	return x = x + y;
}
vec& operator -= (vec& x, vec y) {
	return x = x - y;
}
__int128 cross(vec x, vec y) {
	return (__int128) x.x * y.y - (__int128) x.y * y.x;
}
bool operator < (vec x, vec y) {
	return cross(x, y) < 0;
}
bool operator <= (vec x, vec y) {
	return cross(x, y) <= 0;
}
bool operator > (vec x, vec y) {
	return cross(x, y) > 0;
}
bool operator >= (vec x, vec y) {
	return cross(x, y) >= 0;
}
mt19937 mrand(1);//chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) {return mrand() % (r - l + 1) + l;}
int rt[N], ls[N], rs[N], sz[N];
vec info[N], sum[N];
void pushup(int num) {
	sum[num] = sum[ls[num]] + sum[rs[num]] + info[num];
	sz[num] = sz[ls[num]] + sz[rs[num]] + 1;
}
int merge(int x, int y) {
	if (!x || !y) return x ^ y;
	if (rnd(1, sz[x] + sz[y]) <= sz[x]) return rs[x] = merge(rs[x], y), pushup(x), x;
	return ls[y] = merge(x, ls[y]), pushup(y), y;
}
pair <int, int> split(int num, vec t) {
	if (!num) return make_pair(0, 0);
	if (info[num] > t) {
		pair <int, int> ret = split(ls[num], t);
		ls[num] = ret.second;
		pushup(num);
		return make_pair(ret.first, num);
	} else {
		pair <int, int> ret = split(rs[num], t);
		rs[num] = ret.first;
		pushup(num);
		return make_pair(num, ret.second);
	}
}
int split2(int num, vec& x) {
	if (!num) return 0;
	if ((x + sum[ls[num]]) > info[num]) {
		x += sum[ls[num]] + info[num];
		return split2(rs[num], x);
	} else {
		ls[num] = split2(ls[num], x);
		pushup(num);
		return num;
	}
}
vec query(int num, vec x) {
	if (!num) return x;
	// debug << "~ " << ((x + sum[ls[num]]).x) << " " << ((x + sum[ls[num]]).y) << endl;
	if ((x + sum[ls[num]]) < info[num]) return query(ls[num], x);
	// debug << sum[ls[num]].x << " " << sum[rs[num]].x << endl;
	// debug << info[num].x << " " << info[num].y << " " << (x + sum[ls[num]] + info[num]).x << " " << (x + sum[ls[num]] + info[num]).y << endl;
	return query(rs[num], x + sum[ls[num]] + info[num]);
}
void ins(int& num, int x) {
	pair <int, int> g = split(num, info[x]);
	num = merge(merge(g.first, x), g.second);
}
void mer(int& num, int x) {
	if (!x) return;
	mer(num, ls[x]), mer(num, rs[x]);
	ls[x] = rs[x] = 0, pushup(x);
	ins(num, x);
}
// void dd(int x) {
// 	if (!x) return;
// 	dd(ls[x]);
// 	// debug << info[x].x << " " << info[x].y << endl;
// 	dd(rs[x]);
// }
frac trans(vec x) {
	return (frac) {x.y, x.x};
}
void dfs(int x) {
	for (int i: e[x]) {
		dfs(i);
		if (sz[rt[x]] < sz[rt[i]]) swap(rt[x], rt[i]);
		// debug << sz[rt[x]] << ' ' << sz[rt[i]] << endl;
		mer(rt[x], rt[i]);
		// debug << x << " " << sz[rt[x]] << endl;
	}
	for (int i: v[x]) info[x] += (vec) {1, a[i]};//, debug << "~ " << i << " " << a[i] << endl;
	// debug << "~ " << info[x].x << ' ' << info[x].y << endl;
	// dd(rt[x]);
	rt[x] = split2(rt[x], info[x]);
	// debug << "@ " << info[x].x << " " << info[x].y << " " << sz[rt[x]] << endl;
	// dd(rt[x]);
	sz[x] = 1, sum[x] = info[x];
	ins(rt[x], x);
	// dd(rt[x]);
	ans[x] = trans(query(rt[x], (vec) {2, a[l[x]] + a[r[x]]}));
	// debug << "#  " << query(rt[x], (vec) {2, a[l[x]] + a[r[x]]}).x << " " << query(rt[x], (vec) {2, a[l[x]] + a[r[x]]}).y << endl;
	// debug << "! " << x << ' ' << l[x] << ' ' << r[x] << " " << ans[x].x << " " << ans[x].y << endl;
	// debug << sz[rt[x]] << endl;
	// debug << rt[x] << endl;
	// debug << "! " << info[rt[x]].x << ' ' << info[rt[x]].y << endl;
}
struct hsh {
	ull operator () (pair <int, int> x) const {
		return ((ull) x.first << 32) | x.second;
	}
};
unordered_map <pair <int, int>, int, hsh> gg;
void initialize(std::vector<int> A) {
	n = A.size();
	F(i, 1, n) mp[a[i] = A[i - 1]].push_back(i), s[i] = s[i - 1] + a[i];//, val[i] = mrand();
	s[n + 1] = s[n];
	set <int> s;
	s.insert(0);
	s.insert(n + 1);
	id[0] = ++tot;
	l[1] = 0, r[1] = n + 1;
	for (auto [i, j]: mp) {
		set <int> w;
		for (int k: j) {
			int g = *prev(s.lower_bound(k));
			w.insert(id[g]);
			v[id[g]].push_back(k);
		}
		for (int k: w) {
			int lst = l[k];
			for (int t: v[k]) {
				if (lst + 1 != t) {
					e[k].emplace_back(id[lst] = ++tot);
					l[tot] = lst;
					r[tot] = t;
				}
				lst = t;
			}
			if (lst + 1 != r[k]) {
				e[k].emplace_back(id[lst] = ++tot);
				l[tot] = lst;
				r[tot] = r[k];
			}
		}
		for (int k: j) s.insert(k);
	}
	F(i, 1, tot) {
		// t[i] = tt[i] = {::s[r[i] - 1] - ::s[l[i]], r[i] - l[i] - 1};
		// dot[i] = make_pair(r[i] - l[i] + 1, ::s[r[i]] - (l[i] == 0 ? 0 : ::s[l[i] - 1]));
		gg[make_pair(l[i], r[i])] = i;
	}
	dfs(1);
}
array <ll, 2> maximum_average(int l, int r) {
	l++, r++;
	if (l + 1 == r) {
		frac ans = {a[l] + a[r], 2};
		return {ans.x, ans.y};
	}
	int id = gg[make_pair(l, r)];
	return {ans[id].x, ans[id].y};
}
/* why?
*/