Let us examine the way \(f(a)\) behaves.
Let \(m\) be the maximum value of an element in \(a\). Then, \(a_1\) gets added by \(m\).
Here, since we have \(a_1 > 0\), \(a_1\) will now be the maximum element in \(a\). Similarly, \(a_i\) will be the maximum element in \(a\) when it has just get added.
Thus, we have \(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\), where \(n\) is the length of \(n\).

Now, let us consider compute \(f(a)\) each time after adding an element at the end of \(a\).
Assume that we are now adding \(x\) at the end of \(a\) whose current length is \(n\). We should do the following re-calculation:

• We compute the term \(nm\) each time after updating \(m\).
• The increase of \(n\) by \(1\) increases the value \(na_1 + (n - 1)a_2 + (n - 2)a_3 + \dots + 1 \cdot a_n\) by \(a_1 + a_2 + a_3 + \dots + a_n\), so we maintain this value and add it.
• We have a new term \(1 \cdot a_{n + 1} = x\), which we should add.

In summary, we can solve the problem by updating the value \(f(a)\) while maintaining the sum and maximum value of \(A_1, A_2, A_3, \dots, A_i\), in \(O(N)\) time.