答えで二分探索を行います． 同じ数の書かれたボールの個数を \(d\) 以下にできるか，という問題を考えます．

数列を前から処理していき，添え字 \(i\) まで処理したとします． このとき必要な情報は，

• \(i \to i+0.5\) に使ったボールの個数 \(x\)
• 今までマッチングせずに残っているボールの数 \(y\)

の \(2\) つです． これらの \((x,y)\) の集合は，以下の性質を満たしています．

• \(x\) としてありうる最小値，最大値を \(x_{min},x_{max}\) とする．
• ある \(x\) を固定したときに，ありうる \(y\) の最小値，最大値をそれぞれ \(g(x),f(x)\) とする．
• \(g(x_{min}) \leq g(x)\) for all valid \(x\)
• \(f(x)\) は広義単調増加な上凸関数である．

この性質が成り立つことは，帰納的に証明できます． つまり，ある \(i\) でこの性質が成り立っているとき，\(A_{i+1}\) を処理したあともこの性質が成り立つことが確認できます． （具体的な処理は後述します）

この性質を認めると，保持すべきデータは \(x_{min},x_{max},g(x_{min}),f(x)\) であるとわかります．

\(A_{i+1}\) の処理を考えます． ある \((x,y)\) を採用して，\(i+1 \to i+0.5\) に \(v\) 個のボールを使ったとします．

この時

• \(0 \leq v \leq A_{i+1}\)
• \(v+x \leq d\)
• \(v \leq y\)

を満たす必要があり，その結果 \((x,y)\) は \((A_{i+1}-v,y+A_{i+1}-2v)\) に変化します．

ある \((x,y)\) が valid である場合，任意の \(x'\) (\(x<x'\)) について，\((x',y)\) をvalid な状態としても問題ありません． そこで，\(f(x)=f(x_{max})\) (\(x_{max}<x\)) であるとみなし，\(x\) の上限を取り払うことで，\(v+x \leq d\) を \(v+x=d\) と限定してもよくなります．

すると操作は

• \(x \leq d\)
• \(d-x \leq A_{i+1}\) \(\iff\) \(d-A_{i+1} \leq x\)
• \(d-x \leq y\) \(\iff\) \(d \leq x+y\)

を満たす \((x,y)\) を \((A_{i+1}-d+x,y+A_{i+1}-2d+2x)\) に移動させるという処理になります．

まず，最初の \(2\) つの条件は \(x\) の上限と下限を定めており，これは単に \(f(x)\) の定義域を制限する操作です． \(3\) 番目の操作は \(x+y\) の下限を定めています． これを処理した後は一時的に，\((x,y)\) の集合が最初に述べた性質を満たさなくなります． より具体的には，\(g(x) < g(x_{min})\) となることがあります． ただし，\(g(x)\) は \((x_{min},g(x_{min})-1)\) を通る傾き\(-1\) の一次関数で下から抑えられます． そして，\((A_{i+1}-d+x,y+A_{i+1}-2d+2x)\) に移動するという操作を行ったあとは，\(g(x) \geq g(x_{min})\) が必ず成立するようになります．

結局必要なのは，

• \(f(x)\) の定義域を制限
• \(f(x)\) を平行移動
• \(f(x)+=2x\)

という操作です． \(f(x)\) を区分的一次関数として deque で管理し，全体に適用すべきアフィン変換を別に持つと，すべての操作が効率的に行えます． deque に対する push が高々 \(O(N)\) 回なので，計算量は \(O(N)\) になります．

答えの二分探索を考慮すると，計算量は全体で \(O(N \log \max(A_i))\) です．

writer解(C++)