34626번 - Increase or Smash 다국어

Geumjae has an array $a$ consisting of $n$ zeros. His goal is to transform it into a given target array using a minimum number of operations.

He can perform the following two types of operations any number of times, in any order:

1. Increase: Choose any positive integer $x$. Increase all elements of the array $a$ by $x$. In other words, he chooses a positive integer $x$, and for each $i$ ($1 \le i \le n$), he replaces $a_i$ with $a_i + x$.
2. Smash: Set some elements (possibly none or all) of the array $a$ to $0$. In other words, for each $i$ ($1 \le i \le n$), he either replaces $a_i$ with $0$ or leaves it as before.

Given the final target state of the array $a$, find the minimum total number of operations (both Increase and Smash) Geumjae needs to perform.

It can be shown that for any given final array, a sequence of operations always exists.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line contains a single integer $n$ ($1 \le n \le 100$) --- the number of elements in the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 100$) --- the elements of the target array $a$.

For each test case, output a single integer --- the minimum number of operations required.

Explanation of the first test case:

The target array is $[1, 1, 3]$. A possible sequence of 3 operations (which is the minimum) is:

• Initially, the array is $[0, 0, 0]$. After an Increase operation with $x = 2$, the array becomes $[2, 2, 2]$.
• Next, after a Smash operation on the first two elements, the array becomes $[0, 0, 2]$.
• Finally, after an Increase operation with $x = 1$, the array becomes $[1, 1, 3]$.

We used $2$ Increase operations and $1$ Smash operation for a total of $3$ operations.

Explanation of the second test case:

The target array is $[100]$. A single Increase operation with $x = 100$ gives the target array.