Mental Monumental (Hard Version)

Observation 1: what can one number become?

Take one value $x$ and choose any $b\ge 1$. What values can $x \bmod b$ be?

A value $y$ is achievable iff:

• $y=x$ by choosing any $b>x$;
• or $y<x$ and there exists some $b>y$ with $x \equiv y \pmod b$.

If $x \bmod b = y$, then

$$x-y = kb \quad (k\ge 1), \qquad b>y.$$

So necessarily $x-y > y$, i.e.

$$x \ge 2y+1.$$

And that condition is also sufficient: choose

$$b=x-y,$$

then $b>y$ and $x \bmod b = y$.

So an element $x$ can produce exactly the values

$$\{x\} \cup [0, \lfloor (x-1)/2\rfloor].$$

Equivalently, for a target $y$:

$$x \text{ can produce } y \iff x=y \text{ or } x\ge 2y+1.$$

That’s the whole damn problem in one line.

---

Observation 2: if $y<M$ exists, keep one copy as $y$

Suppose we want to make all values $0,1,\dots,M-1$ appear.

Claim: in some optimal construction, for every value $y<M$ that is present in the array, one copy of $y$ is used to produce exactly $y$.

Why? Suppose not. Then target $y$ is covered by some other element $x\neq y$, so we must have $x\ge 2y+1$. Meanwhile the actual value $y$ is either unused or used to produce some smaller value $z<y$.

Now swap:

• use the real $y$ to produce $y$;
• use $x$ to produce $z$.

This is valid because

$$x \ge 2y+1 > 2z+1,$$

so $x$ can also produce $z$.

So reserving one copy of each present $y<M$ for itself is never worse. No black magic, just a clean exchange argument.

---

Observation 3: reduce to missing values and donor capacities

After reserving one copy of every present value in $[0,M-1]$, the only targets still missing are those $y<M$ with $\operatorname{cnt}_y=0$.

What about the remaining elements? Each leftover element $x$ can produce any value up to

$$r(x)=\left\lfloor\frac{x-1}{2}\right\rfloor.$$

So it acts like a donor for any target in the interval $[0,r(x)]$.

Now we just need to match each missing target to a distinct donor whose capacity is large enough. That’s a standard interval matching situation.

For such intervals $[0,r]$, feasibility is equivalent to checking every suffix: for every $t$,

the number of missing targets in $[t,M-1]$ must be at most the number of donors with capacity at least $t$.

Let’s write that down.

---

Observation 4: the suffix condition simplifies beautifully

Fix $t$.

Missing targets in $[t,M-1]$

There are $M-t$ values there total, and exactly

$$\#\{x\in[t,M-1]: \operatorname{cnt}_x>0\}$$

of them are already present. So the number of missing ones is

$$(M-t)-\#\{x\in[t,M-1]: \operatorname{cnt}_x>0\}.$$

Donors with capacity at least $t$

An element $x$ has capacity at least $t$ iff

$$\left\lfloor\frac{x-1}{2}\right\rfloor \ge t \iff x\ge 2t+1.$$

Among those elements, if $x\in[2t+1,M-1]$ and value $x$ exists, one copy of $x$ was reserved for itself, so only the rest are available as donors. Thus the number of available donors is

$$\#\{a_i\ge 2t+1\}-\#\{x\in[2t+1,M-1]: \operatorname{cnt}_x>0\}.$$

Feasibility gives

$$\#\{a_i\ge 2t+1\}-\#\{x\in[2t+1,M-1]: \operatorname{cnt}_x>0\} \ge (M-t)-\#\{x\in[t,M-1]: \operatorname{cnt}_x>0\}.$$

Rearrange:

$$M \le t + \#\{a_i\ge 2t+1\} + \#\{x\in[t,2t]: \operatorname{cnt}_x>0\}.$$

This must hold for every $t$. So the maximum possible $M$ is

$$f = \min_{t\ge 0}\left(t + \#\{a_i\ge 2t+1\} + \#\{x\in[t,2t]: \operatorname{cnt}_x>0\}\right).$$

That’s the formula. The monster is slain.

---

Observation 5: how does one appended value change the formula?

For each prefix, define

$$val[t] = t + A[t] + B[t],$$

where

• $A[t] = \#\{a_i\ge 2t+1\}$,
• $B[t] = \#\{x\in[t,2t]: \operatorname{cnt}_x>0\}$.

Then the answer for the current prefix is just

$$\min_t val[t].$$

Now append a new value $x$.

Effect on $A[t]$

The new element contributes to $A[t]$ iff

$$x\ge 2t+1 \iff t\le \left\lfloor\frac{x-1}{2}\right\rfloor.$$

So we add $1$ to all $t$ in the range

$$[0,\lfloor (x-1)/2\rfloor].$$

Effect on $B[t]$

This depends only on whether $x$ is present at least once. So only the first occurrence of $x$ matters. If it is the first occurrence, then $x$ belongs to interval $[t,2t]$ exactly when

$$t\le x\le 2t \iff \left\lceil\frac{x}{2}\right\rceil \le t \le x.$$

So we add $1$ to all $t$ in

$$[\lceil x/2\rceil, x].$$

That’s two range-add updates per element, and after each prefix we need the global minimum. Classic segment tree with lazy propagation:

• initial array is $val[t]=t$,
• do range add,
• query global min.

---

Correctness sketch

We proved:

1. A value $x$ can produce exactly $y$ iff $x=y$ or $x\ge 2y+1$.
2. For any feasible mex $M$, we may assume one copy of every present value $y<M$ is used to realize $y$ itself.
3. The remaining missing values are matched to leftover donors with capacities $r(x)=\lfloor (x-1)/2\rfloor$.
4. Interval matching of missing targets to donors is feasible iff every suffix $[t,M-1]$ has enough donors, which simplifies to $$M \le t + \#\{a_i\ge 2t+1\} + \#\{x\in[t,2t]:\operatorname{cnt}_x>0\}$$ for every $t$.
5. Therefore $$f = \min_t \left(t + \#\{a_i\ge 2t+1\} + \#\{x\in[t,2t]:\operatorname{cnt}_x>0\}\right).$$
6. Appending a value updates this expression by two simple range increments, so a lazy segment tree maintains the minimum for every prefix.

Done. No DP acrobatics, no cursed flow, just a clean invariant and a segment tree beating the hell out of range updates.

---

Complexity

Let $V = \max a_i$ in one test case.

• Building the segment tree over $t=0..V$: $O(V)$.
• Each appended value performs at most two range-add updates: $O(\log V)$.
• Querying the answer is just the root minimum: $O(1)$.

So each test runs in

$$O(V + n\log V),$$

and over all tests the total is safe because

$$\sum n \le 2\cdot 10^5, \qquad \sum V \le 10^6.$$

Memory is $O(V)$.

Very comfortable under the limits.