Increase or Smash

Let the distinct values in the target array be

$v_1 < v_2 < \dots < v_k.$

The answer is:

$2k - 1$

where $k$ is the number of distinct values in the array.

Why distinct values are all that matter

The positions do not matter at all. A smash operation can reset any subset of elements, so we can freely choose which elements belong to which final value group.

The only real question is: how many different final values do we need to manufacture?

If two elements both need value $7$, they can always be treated the same way. If one needs $3$ and another needs $10$, then they must have different histories: the $10$ element must keep some earlier increase that the $3$ element loses by being smashed.

What an element's final value means

Suppose we do several global increases. If an element is smashed at some point, everything it gained before that smash is erased. So its final value is exactly the sum of the increases that happened after its last smash.

That means different target values correspond to different suffix sums of the increase sequence.

Since every increase amount is positive, these suffix sums are strictly different as you include more increases. So to get $k$ different positive values, we need at least $k$ increase operations.

That gives the first lower bound:

$\text{operations} \ge k.$

But increases alone make all elements equal. To split elements into different value groups, we also need smashes.

Each smash can create one new “restart point” in time. With $s$ smashes, an element can have one of at most $s+1$ possible last-smash times: never smashed, after smash 1, after smash 2, and so on. Therefore, to create $k$ different final values, we need at least $k-1$ smashes.

So every solution needs at least

$k + (k-1) = 2k-1$

operations.

Construction

Now we show $2k-1$ is always enough, so the lower bound is tight.

Let the distinct target values be sorted increasingly:

$v_1 < v_2 < \dots < v_k.$

We build from largest value down to smallest value.

1. First increase all elements by $v_k - v_{k-1}$.
2. Smash all elements whose final value should be at most $v_{k-1}$.
3. Increase by $v_{k-1} - v_{k-2}$.
4. Smash all elements whose final value should be at most $v_{k-2}$.
5. Continue this pattern.
6. Finally increase by $v_1$.

More cleanly, the increase amounts are:

$v_k-v_{k-1},\ v_{k-1}-v_{k-2},\ \dots,\ v_2-v_1,\ v_1.$

After each of the first $k-1$ increases, we smash exactly the elements that should end with one of the smaller remaining values.

An element targeting $v_j$ skips the early increases that are meant only for values larger than $v_j$, then keeps the remaining increases:

$v_j-v_{j-1} + v_{j-1}-v_{j-2} + \dots + v_1 = v_j.$

Telescoping saves the day. Math doing unpaid labor, classic.

So $k$ increases and $k-1$ smashes are enough, for a total of:

$2k-1.$

Algorithm

For each test case:

1. Read $n$.
2. Insert all $a_i$ into a set.
3. Let $k$ be the size of the set.
4. Print $2k-1$.

Constraints are tiny, so this is comfortably overkill in the best way.

Complexity:

$O(n \log n)$

per test case using a set, or basically instant for $n \le 100$.