計算量解析が本質の問題だね

解法

まず $a _ {i}$ がどこまでの範囲で最大値になるかを求めよう！

これはstackを使うことで $O(n)$ でできることは有名である。

そうすると $a _ {i}$ より左のパートと $a _ {i}$ より右のパートから1つずつとってきて和が $a _ {i}$ になるような数を調べたらいい。

一見 $O(n ^ 2)$ に見えるが、実は左のパートと右のパートの小さいほうをみることで $O(n \log n)$ になる。

実際になめる要素が各区間の半分以下になっていくからだ！

このことから、各要素はせいぜい $O(\log n)$ 回しかなめられず、よって全体の計算量としては $O(n \log n)$ になる

提出コード

マージテクとかと似たような感じだね