[Solution] Tokitsukaze and All Zero Sequence solution codeforces

Tokitsukaze and All Zero Sequence solution codeforces – Tokitsukaze has a sequence 𝑎a of length 𝑛n. For each operation, she selects two numbers 𝑎𝑖ai and 𝑎𝑗aj (𝑖𝑗i≠j1𝑖,𝑗𝑛1≤i,j≤n).

  • If 𝑎𝑖=𝑎𝑗ai=aj, change one of them to 00.
  • Otherwise change both of them to min(𝑎𝑖,𝑎𝑗)min(ai,aj).

[Solution] Tokitsukaze and All Zero Sequence solution codeforces

Tokitsukaze wants to know the minimum number of operations to change all numbers in the sequence to 00. It can be proved that the answer always exists.

Input

The first line contains a single positive integer 𝑡t (1𝑡10001≤t≤1000) — the number of test cases.

For each test case, the first line contains a single integer 𝑛n (2𝑛1002≤n≤100) — the length of the sequence 𝑎a.

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖1000≤ai≤100) — the sequence 𝑎a.

[Solution] Tokitsukaze and All Zero Sequence solution codeforces

For each test case, print a single integer — the minimum number of operations to change all numbers in the sequence to 00.

Example
input

Copy
3
3
1 2 3
3
1 2 2
3
1 2 0
output

Copy
4
3
2

[Solution] Tokitsukaze and All Zero Sequence solution codeforces

In the first test case, one of the possible ways to change all numbers in the sequence to 00:

In the 11-st operation, 𝑎1<𝑎2a1<a2, after the operation, 𝑎2=𝑎1=1a2=a1=1. Now the sequence 𝑎a is [1,1,3][1,1,3].

In the 22-nd operation, 𝑎1=𝑎2=1a1=a2=1, after the operation, 𝑎1=0a1=0. Now the sequence 𝑎a is [0,1,3][0,1,3].

In the 33-rd operation, 𝑎1<𝑎2a1<a2, after the operation, 𝑎2=0a2=0. Now the sequence 𝑎a is [0,0,3][0,0,3].

In the 44-th operation, 𝑎2<𝑎3a2<a3, after the operation, 𝑎3=0a3=0. Now the sequence 𝑎a is [0,0,0][0,0,0].

So the minimum number of operations is 44.

For Solution

Click here

Leave a Comment