We perform binary search on the answer. Consider the problem of whether we can make the number of balls with the same number written on them at most \(d\).

We process the sequence from the beginning, and suppose we have processed up to index \(i\). At this point, the necessary information consists of two items:

• The number of balls \(x\) used for \(i \to i+0.5\)
• The number of balls \(y\) that remain unmatched so far

The set of these \((x,y)\) satisfies the following properties:

• Let \(x_{min}\) and \(x_{max}\) be the minimum and maximum possible values of \(x\).
• When we fix some \(x\), let \(g(x)\) and \(f(x)\) be the minimum and maximum possible values of \(y\), respectively.
• \(g(x_{min}) \leq g(x)\) for all valid \(x\).
• \(f(x)\) is a non-decreasing concave function.

These properties can be proved inductively. That is, when these properties hold for some \(i\), we can confirm that these properties still hold after processing \(A_{i+1}\). (The specific processing is described later.)

Accepting these properties, we understand that the data we need to maintain is \(x_{min}, x_{max}, g(x_{min}), f(x)\).

Let us consider processing \(A_{i+1}\). Suppose we adopt some \((x,y)\) and use \(v\) balls for \(i+1 \to i+0.5\).

In this case, we need to satisfy:

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

As a result, \((x,y)\) changes to \((A_{i+1}-v, y+A_{i+1}-2v)\).

When some \((x,y)\) is valid, for any \(x'\) (\(x < x'\)), there is no problem in making \((x',y)\) a valid state as well. Therefore, by considering \(f(x) = f(x_{max})\) (\(x > x_{max}\)) and removing the upper bound on \(x\), we can restrict \(v+x \leq d\) to \(v+x = d\).

Then, the operation becomes moving \((x,y)\) that satisfies:

• \(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\)

to \((A_{i+1}-d+x, y+A_{i+1}-2d+2x)\).

First, the first two conditions determine the upper and lower bounds of \(x\), which is simply an operation to restrict the domain of \(f(x)\). The third operation determines the lower bound of \(x+y\). After processing this, temporarily, the set of \((x,y)\) no longer satisfies the properties mentioned at the beginning. More specifically, \(g(x) < g(x_{min})\) may occur. However, \(g(x)\) is bounded from below by a linear function with slope \(-1\) passing through \((x_{min}, g(x_{min})-1)\). Then, after performing the operation of moving to \((A_{i+1}-d+x, y+A_{i+1}-2d+2x)\), \(g(x) \geq g(x_{min})\) will always hold.

What we ultimately need are the operations:

• Restricting the domain of \(f(x)\)
• Translating \(f(x)\) in parallel
• \(f(x) += 2x\)

By managing \(f(x)\) as a piecewise linear function with a deque and separately maintaining the affine transformation to be applied globally, all operations can be performed efficiently. There are at most \(O(N)\) pushes to the deque, so the time complexity is \(O(N)\).

Considering the binary search on the answer, the overall time complexity is \(O(N \log \max(A_i))\).

Writer’s solution (C++)