由于没有 OJ 只能写题意了

题意：

给定一个长度为 $n$ 的序列，求区间 $[l,r]$ 内的 $a < b$ 满足 $\frac{\sum_{i=a}^b A_i}{b-a}$ 最大

也就是区间和除以区间长度减 $1$ 尽量小。

显然可以考虑前缀和，然后就是 $\frac{S_b - S_{a-1}}{b-a}$ 。我们考虑每个点维护两类点，一类 $A(a,S_a)$ 一类 $B(b,S_{b-1})$。

然后问题就转化成了区间内选择一个靠前的 $B$ 类点，一个靠后的 $A$ 类点，求这两个点的最大斜率。

首先考虑如果只有一次询问怎么做。这是一个经典的问题，有一种很仙的线形做法。首先，直接对这个点前面的 $B$ 点建凸包并在凸包上二分是可以的，但是复杂度会带一个 $\log$ （而且我场上这个东西还没写挂了）。但是，sjx 教了我一种很神仙的线形做法。考虑由于 $x$ 坐标单调递增，虽然 $y$ 坐标的变化无规律，但是我们仍然可以确定，在维护凸包的队首不优于第二个值的时候，队首就可以弹掉了。这样可能会导致局部的最优值挂掉，但是一定可以找到全局的最优解。因为这个东西挂掉的情况一定是两个最优线出现了一个交叉状的东西，但是后面的一定不优于前面的。（大概也可以画图感性理解一下）。

于是我们现在得到了一个 $O(nq)$ 的做法。可以通过前 $40\%$ 的数据。然后最开始数据太水被 $n^2$ 或者 $nq$ 水到了 $70$ 甚至 $100$ 。。后来加强数据只能 $40$ 了。

然后考虑，如果询问组数很多。首先可以分块，块内预处理出最优答案。然后：

设块大小是 $B$ 。

如果询问的两个位置在同一个块内，直接暴力，复杂度 $O(B)$ 。

考虑对于询问的两个位置不在同一个块内。

对于中间的整块，我们考虑对从每个块的左端点和右端点分别向右向左扫一遍处理出每个位置的最优解和前缀后缀 $\max$ ，于是整块对整块以及整块对散块的询问复杂度就是 $O(1)$ ，预处理复杂度是 $O(\frac{n^2}{B})$ 。

然后考虑两边零散的部分，不难发现它们关于整块的答案已经被解决了，于是现在的问题就只有零散块之间的部分。我们可以把它们拼在一起暴力做一遍，复杂度 $O(B)$

于是复杂度是 $O(qB + \frac{n^2}{B})$ ，如果设 $B = \sqrt n$ 大概复杂度就是 $O(n\sqrt n + q\sqrt n)$ 了。

空间复杂度是 $O(n\sqrt n)$ 左右，因为维护了两个数组很容易爆炸，块大小设得大一点就好了。（本身这题 $q$ 很小所以块设大一点也快一些）。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 100006
#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , q , blo , bel[MAXN];
ll S[MAXN];

struct poi {
	int x , y;
	poi( ) { x = y = 0; }
	poi( int a , int b ) : x(a) , y(b) {}
} A[MAXN] , B[MAXN] ;

ll gcd( ll a , ll b ) {
	return !b ? a : gcd( b , a % b );
}

struct frac {
	ll x , y;
	frac( ) : x(0) , y(0) {}
	frac( ll a , ll b ) : x(a) , y(b) { if( y < 0 ) x = -x , y = -y; }
	bool operator < ( const frac a ) const {
		return !y || x * a.y < y * a.x;
	}
	void ot( ) {
		ll g = gcd( abs( x ) , abs( y ) );
		printf("%lld/%lld\n",x / g,y / g);
	}
};

frac pr[61][MAXN] , su[61][MAXN];

int que[MAXN] , hd , tl;
frac brul( int l , int r , int t = 0 , frac *as = nullptr , int kk = 0 ) {
	frac mx;
	if( !kk ) hd = 0 , tl = -1;
	rep( i , l , r ) {
		while( hd < tl && frac( B[que[hd]].y - A[i].y , B[que[hd]].x - A[i].x ) < frac( B[que[hd + 1]].y - A[i].y , B[que[hd + 1]].x - A[i].x ) ) ++ hd;
		if( hd <= tl ) mx = max( mx , frac( B[que[hd]].y - A[i].y , B[que[hd]].x - A[i].x ) );
		while( hd < tl && frac( B[que[tl]].y - B[i].y , B[que[tl]].x - B[i].x ) < frac( B[que[tl - 1]].y - B[i].y , B[que[tl - 1]].x - B[i].x ) ) -- tl;
		que[++ tl] = i;
		if( t ) as[i] = mx;
	}
	return mx;
}
frac brur( int l , int r , int t = 0 , frac *as = nullptr ) {
	frac mx;
	hd = 0 , tl = -1;
	que[++ tl] = r;
	per( i , r - 1 , l ) {
		while( hd < tl && frac( A[que[hd]].y - B[i].y , A[que[hd]].x - B[i].x ) < frac( A[que[hd + 1]].y - B[i].y , A[que[hd + 1]].x - B[i].x ) ) ++ hd;
		mx = max( mx , frac( A[que[hd]].y - B[i].y , A[que[hd]].x - B[i].x ) );
		while( hd < tl && frac( A[que[tl]].y - A[i].y , A[que[tl]].x - A[i].x ) < frac( A[que[tl - 1]].y - A[i].y , A[que[tl - 1]].x - A[i].x ) ) -- tl;
		que[++ tl] = i;
		if( t ) as[i] = mx;
	}
	return mx;
}

void solve() {
	cin >> n >> q;
	blo = 1700;
	rep( i , 1 , n ) scanf("%lld",S + i) , S[i] += S[i - 1] , A[i] = poi( i , S[i] ) , B[i] = poi( i , S[i - 1] );
//	rep( i , 59 , 71 ) printf("%lld ",S[i]);puts("");
//	rep( i , 1 , q ) {
//		int l , r;
//		scanf("%lld%lld",&l,&r);
//		brul( l , r ).ot( );
//	}
	rep( i , 1 , n ) bel[i] = ( i - 1 ) / blo + 1;
	for( int i = 1 ; i <= n ; i += blo ) {
		brul( i , n , 1 , pr[bel[i]] );
		brur( 1 , bel[i] * blo , 1 , su[bel[i]] );
	}
	rep( i , 1 , q ) {
		int l , r;
		scanf("%lld%lld",&l,&r);
		if( bel[l] == bel[r] ) brul( l , r ).ot( );
		else {
			frac mx;
			mx = brul( l , bel[l] * blo );
			mx = max( mx , brul( ( bel[r] - 1 ) * blo + 1 , r , 0 , nullptr , 1 ) );
			if( bel[l] + 1 < bel[r] )
				mx = max( mx , max( pr[bel[l] + 1][r] , su[bel[r] - 1][l] ) );
			mx.ot( );
		}
	}
}

signed main() {
	freopen("profit.in","r",stdin);
	freopen("profit.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}