Mental Monumental (Easy Version)

Observation 1: what can one element become?

Take one number $x$. We choose any integer $b \ge 1$, and the value becomes $x \bmod b$.

What results are possible?

• Getting $x$ itself is easy: choose any $b>x$, then $x \bmod b = x$.
• For some smaller value $y<x$, suppose $x \bmod b = y$. Then $x-y = kb$ for some integer $k\ge 1$. Also a remainder must satisfy $y<b$. Therefore $x-y \ge b > y,$ so $x>2y.$

That gives a necessary condition.

Is it sufficient? Yep. If $x>2y$, choose $b=x-y.$ Then $b>y$, so the remainder is valid, and $x \bmod (x-y) = y.$

So the reachable values from $x$ are exactly $\{x\}\cup\{0,1,2,\dots,\lfloor (x-1)/2\rfloor\}.$

That’s the whole damn problem in one line.

---

Observation 2: checking whether mex $m$ is possible

To make $\operatorname{mex}=m$, we need every value $0,1,\dots,m-1$ to appear after the operation.

Each array element can be used once, so this is a matching problem.

An element with value $v$ can produce a target value $x$ iff $v=x \quad\text{or}\quad v\ge 2x+1.$

So for a fixed $m$, the question becomes:

Can we assign distinct array elements to all targets $0,1,\dots,m-1$ under that rule?

This feasibility is monotone: if we can make mex $m$, then we can obviously make any smaller mex too. So binary search is fair game.

---

Observation 3: reserve exact copies first

This is the key exchange argument that saves us from writing cursed nonsense.

Suppose some value $x<m$ appears in the array. Then there exists an optimal construction where one copy of $x$ is left as $x$.

Why is that always safe?

Assume in some solution a copy of $x$ is used to make some smaller value $y$, and some other element $v$ is used to make $x$.

Since $x$ is produced by $v$ and $v\ne x$, we must have $v\ge 2x+1.$

Since the copy of $x$ makes $y<x$, we know $x>2y.$ So $v\ge 2x+1 > 2y+1,$ meaning $v$ can also make $y$.

Therefore we can swap roles:

• use the copy of $x$ to make $x$,
• use $v$ to make $y$.

Nothing breaks.

So for a fixed $m$:

• for every present value $x\in[0,m-1]$, reserve one copy of $x$ to cover $x$ itself;
• the values in $[0,m-1]$ that are absent are the only ones we still need to create.

Now the remaining copies are just a pool of leftovers. A missing value $x$ can be made by a leftover value $v$ iff $v\ge 2x+1.$

---

Greedy check for a fixed $m$

After reserving one copy of each present value in $[0,m-1]$:

• let the missing targets be $x_1 < x_2 < \dots < x_k;$
• let the leftover values, sorted, be $v_1 \le v_2 \le \dots \le v_t.$

We need to match each $x_i$ with a distinct leftover $v_j$ such that $v_j \ge 2x_i+1.$

The greedy strategy is standard and correct:

• process missing values from small to large;
• for each missing $x$, take the smallest leftover value $v$ with $v\ge 2x+1$.

Why? Because larger missing values only have stricter requirements. Burning a too-large leftover early is just self-sabotage. Classic greedy, classic not-being-an-idiot.

If at some step no leftover satisfies the threshold, then mex $m$ is impossible.

---

How to implement the check in $O(n)$ after sorting

Sort the array once.

For a given $m$, scan the sorted array by groups of equal values. During this scan you can build two sorted lists directly:

1. missing: all values in $[0,m-1]$ that do not appear;
2. leftover: all array elements except one reserved copy of each present value in $[0,m-1]$.

Both lists are naturally sorted. Then run a two-pointer greedy match.

So:

• sorting: $O(n\log n)$,
• one feasibility check: $O(n)$,
• binary search over the answer: $O(\log n)$ checks.

Total per test case: $O(n\log n).$

Given $\sum n \le 2\cdot 10^5,$ this flies comfortably.

---

Correctness sketch

We proved:

1. A value $v$ can become exactly the set $\{v\}\cup [0,\lfloor (v-1)/2\rfloor].$
2. For any feasible mex $m$, we may reserve one copy of every present $x<m$ to realize $x$ exactly.
3. Therefore the remaining task is only to cover missing values $x$ using leftovers with threshold $v\ge 2x+1.$
4. The smallest-suitable-leftover greedy is optimal for such threshold matching.

Hence the check is correct, and binary search over $m$ returns the maximum feasible mex, which is exactly $f(a)$.

---

Complexity

For each test case:

• sort once: $O(n\log n)$,
• binary search on answer: $O(\log n)$ iterations,
• each check: $O(n)$.

So the total is $O(n\log n).$ Memory usage is $O(n).$

Nice, clean, no black magic, no overengineered garbage.