设(val_{i,j})为区间([l,r])的答案
根据题意，我们可以维护(a_i)和(i* a_i)的前缀和(sum1,sum2)
(val_{l,r}=sum2[r]-sum2[l-1]-(l-1)*(sum1[r]-sum1[l-1]))
我们枚举(r)
对于所有(val_{l',r}le val_{l,r})，有
((l'-1)*sum1_{l'-1}-sum2_{l'-1}-(l'-1)*sum1_rle (l-1)*sum1_{l-1}-sum2_{l-1}-(l-1)*sum1_r)
我们发现这个式子可以斜率优化
斜率优化一般把我们要的最大值/最小值也就是这里的(val_{l,r})放在(b)里面，那么((l-1)*sum1_{l-1}-sum2_{l-1}-(l-1)*sum1_r)就可以表示成(y-kx)，
把跟(r)有关的放在(k)里面，(k=sum1_r)
于是(b=val_{l,r}-sum_r,x=l-1,y=(l-1)*sum1_{l-1})
因为是最大值，我们维护一个上凸壳每次二分找到第一个斜率小于(sun1_r)的位置，然后更新答案即可