\(f(a)\) の挙動を調べます。
\(a\) の要素の最大値を \(m\) とすると、\(a_1\) には \(m\) が足されます。
このときもともと \(a_1 > 0\) なので \(m\) が足された \(a_1\) は \(a\) の要素の最大値となります。同様に、\(a_i\) に足された直後には \(a_i\) が \(a\) の最大値となります。
よって \(f(a) = (a_1 + m) + (a_2 + (a_1 + m)) + (a_3 + (a_2 + (a_1 + m))) \dots = nm + na_1 + (n - 1)a_2 + (n - 2)a_3 + \dots + 1 \cdot a_n\) (ただし \(n\) は \(a\) の長さ) となります。

次に \(a\) の末尾に要素を追加しながら、毎回 \(f(a)\) を計算することを考えます。
今長さ \(n\) の \(a\) の末尾に \(x\) を追加するとき、以下のように再計算するとよいです。

• \(nm\) の項は、\(m\) を更新した上で毎回計算する
• \(na_1 + (n - 1)a_2 + (n - 2)a_3 + \dots + 1 \cdot a_n\) は \(n\) が \(1\) 増えるため \(a_1 + a_2 + a_3 + \dots + a_n\) だけ増えるから、常にこの値を持っておいて足す
• 新たに \(1 \cdot a_{n + 1} = x\) という項が増えるので、\(x\) を足す

まとめると、常に \(A_1, A_2, A_3, \dots, A_i\) の合計及び最大値を持ちながら \(f(a)\) の値を更新していくことで \(O(N)\) で解くことができます。