Convex Hull Trick 的な方針の \(O(N)\) 解法です．

\(1\leq k\leq r\leq N\) に対して

\[\sum_{i=k}^{r}(A_i-x)\geq 0\iff\frac{1}{r-k+1}\sum_{i=k}^{r}A_i\geq x\]

が成り立つことに注意すれば，各 \(k\) に対して求める値は \(\max_{k\leq r\leq N}\sum_{i=k}^{r}(A_i-x)\geq 0\) となる \(x\) の最大値に一致します． さらに折れ線 \(y=\max_{k\leq r\leq N}\sum_{i=k}^{r}(A_i-x)\) の形を考えると，求める値は折れ線 \(y=\max\left(0,\max_{k\leq r\leq N}\sum_{i=k}^{r}(A_i-x)\right)\) の傾きが変化する点のうち \(x\) 座標が最大のものの \(x\) 座標に一致します．

以上から，次のようにすれば本問題は解けます．

• はじめ \(L=\{0\}\) とする．
• \(k=N,N-1,\dots,1\) の順に次を行う．
  • \(L\) を \(\{f(x)+(A_k-x)\mid f(x)\in L\}\) で置き換える．
  • \(L\) に \(0\) を追加する．
  • 折れ線 \(y=\max_{f(x)\in L}f(x)\) の傾きが変化する点のうち，\(x\) 座標が最大のものの \(x\) 座標（\(M(L)\) とおく）を求める．

ここで任意の \(a,b\) に対し \(M(L)=M(\{f(x)+ax+b\mid f(x)\in L\})\) であることに注意すれば，次のようにしても構いません．

• はじめ \(L=\{0\}\) とする．
• \(k=N,N-1,\dots,1\) の順に次を行う．
  • \(L\) に \(\sum_{i=k}^{N}(x-A_i)\) を追加する．
  • 折れ線 \(y=\max_{f(x)\in L}f(x)\) の傾きが変化する点のうち，\(x\) 座標が最大のものの \(x\) 座標を求める．

追加される直線の傾きが単調増加であること，取得クエリでは傾きが大きい方から \(2\) 直線分の情報しか必要ないことから，stack を用いて \(O(N)\) で実装できます．

実装例(C++)