P0797

Almost

Almost

对于 nn 个数 X1,X2,…,XnX_1,X_2,\ldots,X_n（n>1n>1），定义它们的几乎平均数为

∑i=1nXin−1。\frac{\sum_{i=1}^{n}X_i}{n-1}。

给定一个长度为 NN 的序列 SS，回答 QQ 次询问。

每次询问给出两个整数 L,RL,R，满足 1≤L<R≤N1\le L<R\le N。你需要找到两个整数 a,ba,b，满足 L≤a<b≤RL\le a<b\le R，使连续子序列 Sa,Sa+1,…,SbS_a,S_{a+1},\ldots,S_b 的几乎平均数最大。

输入格式

第一行包含两个正整数 N,QN,Q。

第二行包含 NN 个整数，表示序列 SS。

接下来 QQ 行，每行包含两个整数 L,RL,R，表示一次询问。

输出格式

对于每次询问输出一行，用一个既约分数表示最大的几乎平均数。

若答案为整数 xx，则输出 x/1。

样例输入

3 2
-2 -1 -2
1 2
1 3

样例输出

-3/1
-5/2

数据范围

  • 对于所有数据，∣Si∣≤106|S_i|\le 10^6；
  • 测试点 11：N=10N=10，Q=10Q=10；
  • 测试点 22：N=100N=100，Q=100Q=100；
  • 测试点 33：N=1000N=1000，Q=1000Q=1000；
  • 测试点 44：N=2000N=2000，Q=2000Q=2000；
  • 测试点 55：N=5000N=5000，Q=5000Q=5000；
  • 测试点 66：N=104N=10^4，Q=5000Q=5000；
  • 测试点 77：N=104N=10^4，Q=104Q=10^4；
  • 测试点 88：N=2×104N=2\times 10^4，Q=5000Q=5000；
  • 测试点 99：N=2×104N=2\times 10^4，Q=104Q=10^4；
  • 测试点 1010：N=3×104N=3\times 10^4，Q=5000Q=5000；
  • 测试点 1111：N=3×104N=3\times 10^4，Q=104Q=10^4；
  • 测试点 1212：N=4×104N=4\times 10^4，Q=104Q=10^4；
  • 测试点 1313：N=5×104N=5\times 10^4，Q=104Q=10^4；
  • 测试点 1414：N=6×104N=6\times 10^4，Q=2×104Q=2\times 10^4；
  • 测试点 1515：N=7×104N=7\times 10^4，Q=2×104Q=2\times 10^4；
  • 测试点 1616：N=8×104N=8\times 10^4，Q=3×104Q=3\times 10^4；
  • 测试点 1717：N=9×104N=9\times 10^4，Q=3×104Q=3\times 10^4；
  • 测试点 1818：N=105N=10^5，Q=10Q=10；
  • 测试点 1919：N=105N=10^5，Q=3×104Q=3\times 10^4；
  • 测试点 2020：N=105N=10^5，Q=3×104Q=3\times 10^4。

来源与许可

本题题面与测试数据整理自 BZOJ 2670。

样例 1

输入

3 2
-2 -1 -2
1 2
1 3

输出

-3/1
-5/2