Hints: https://atcoder.jp/contests/arc210/editorial/14585

In this editorial, we use the following notation:

• When we simply write \(A_i\), it represents the value of \(A_i\) in the initial state.
• The point in time immediately after \(t\) operations have been performed is called time \(t\).
• We write \(A_{t,i}\) for the value of \(A_i\) at time \(t\).

[1] Organizing the conditions

The condition can be rephrased as: \(A_{t,i} < A_{t,i+1}\) holds for all \(t, i\). So first, let us fix one \(t, i\) and organize the condition that \(A_{t,i} < A_{t,i+1}\) holds.

Let \(s_{t,i}\) denote the total value added to \(A_i\) up to the \(t\)-th operation. Then, since \(A_{t,i}=A_i+s_{t,i}\), we have

\[A_{t,i}<A_{t,i+1}\iff A_{i}+s_{t,i} < A_{i+1}+s_{t,i+1}\iff A_i+(s_{t,i}-s_{t,i+1}) < A_{i+1}.\]

Therefore, if we let \(c_i = \max_t (s_{t,i}-s_{t,i+1})\), then the condition “\(A_i < A_{i+1}\) holds at every time” can be rephrased as \(A_i+c_i<A_{i+1}\).

[2] Computing the answer

From the above, to find the answer, we can proceed as follows:

• For \(i=1,2,\ldots,N-1\), compute \(c_i = \max_t (s_{t,i}-s_{t,i+1})\).
• Define the sequence \(A\) by \(A_1=1\) and the recurrence \(A_{i+1}=A_i+c_i+1\). Then, the sum of \(A\) is the answer.

For computing \(c_i\), we can skip the computation at time \(t+1\) when \(s_{t,i}\) and \(s_{t,i+1}\) are equal at times \(t\) and \(t+1\).

More specifically, we maintain the sequence \(s=(s_{t,1},\ldots,s_{t,N})\) while advancing time (when advancing time by one, we only perform one addition according to the operation). When an addition is performed to the \(i\)-th term, we perform computations related to \(c_{i-1}\) and \(c_i\) (considering that \(s_{i-1}-s_i\) decreases, it also suffices to only compute \(c_i\)).

This allows us to compute the answer in \(O(N+Q)\) time.

• Sample solution: https://atcoder.jp/contests/arc210/submissions/70835729