U138160 总之就是非常舒服
题目背景
供题人 ckw。
在下面有 Sol，可供参考。
题目描述
输入格式
无
输出格式
无
说明/提示
### Sol
贪心结论，区间 $[l,r]$不借助外来帮助，能够自己调整到合法，当且仅当 $\sum_{l\le i\le r} a_i\ge k\times (r-l+1)$。
正确性显然，多出的数字可以在已经合法的部分随意移动，并不断填补到不合法的位置。
最后一定能使整个区间合法。
### 考场
以下是考场上的想法。
考虑二分答案枚举区间长度，枚举区间判断能否使它合法。
判断 区间和，左侧最大后缀和，右侧最大前缀和 之和是否不小于区间长度乘 $k$（固定了区间，因此考虑区间左右侧的贡献）。
三个信息 $O(n)$ 预处理即可。
复杂度 $O(nm\log n)$，常数很小跑了 90/cy
```cpp
//二分答案，暴力
/*
By:Luckyblock
*/
#include
#include
#include
#include
#define LL long long
const int kMaxn = 1e6 + 10;
//===========================================================
int n, m, k, q[kMaxn];
LL a[kMaxn], sum[kMaxn], pre[kMaxn], suf[kMaxn];
bool flag;
//===========================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w