ヒント → https://atcoder.jp/contests/arc210/editorial/14522

本解説において，次のような記号を使います．

• 単に \(A_i\) と書いた場合，初期状態での \(A_i\) の値を表すこととする．
• \(t\) 回の操作が行われた直後の時点を時刻 \(t\) ということとする．
• 時刻 \(t\) における \(A_i\) の値を \(A_{t,i}\) と書く．

[1] 条件の整理

条件は，任意の \(t, i\) に対して \(A_{t,i} < A_{t,i+1}\) が成り立つことと言い換えられます．そこでまず \(t, i\) をひとつ固定して，\(A_{t,i} < A_{t,i+1}\) が成り立つという条件を整理しましょう．

\(t\) 回の操作までで \(A_i\) に加算された値の総和を \(s_{t,i}\) と書くことにします．すると，\(A_{t,i}=A_i+s_{t,i}\) なので，

\[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}\]

と変形できます．

よって，\(c_i = \max_t (s_{t,i}-s_{t,i+1})\) とすれば，「どの時刻においても \(A_i < A_{i+1}\) が成り立つ」という条件は，\(A_i+c_i<A_{i+1}\) と言い換えられます．

[2] 答の計算

以上のことから，答を求めるには次のようにすればよいです．

• \(i=1,2,\ldots,N-1\) に対して，\(c_i = \max_t (s_{t,i}-s_{t,i+1})\) を求める．
• \(A_1=1\) と漸化式 \(A_{i+1}=A_i+c_i+1\) によって数列 \(A\) を定める．このとき \(A\) の総和が答である．

\(c_i\) の計算については，時刻 \(t, t+1\) で \(s_{t,i}, s_{t,i+1}\) が等しい場合に時刻 \(t+1\) での計算を省略するというようにすればよいです．

より詳細には，時刻を進めながら列 \(s=(s_{t,1},\ldots,s_{t,N})\) を保持するようにします（時刻をひとつ進める際に，操作に応じた加算をひとつ行うだけです）．\(i\) 番目の項への加算が行われたときには，\(c_{i-1}\) や \(c_i\) に関する計算を行うようにします（\(s_{i-1}-s_i\) は減少することを考えると，\(c_i\) だけでも十分です）．

これで答を \(O(N+Q)\) 時間で計算できます．

• 解答例：https://atcoder.jp/contests/arc210/submissions/70835729