← 返回题目列表

Codeforces · 1678/A

A. 时风和全零序

中文机器翻译题面 查看原题

Tokitsukaze 有一个长度为 $$$n$$$ 的序列 $$$a$$$。对于每个操作,她选择两个数字 $$$a_i$$$ 和 $$$a_j$$$ ($$$i \ne j$$$; $$$1 \leq i,j \leq n$$$)。

- 如果 $$$a_i = a_j$$$,将其中之一更改为 $$$0$$$。
- 否则将它们都更改为 $$$\min(a_i, a_j)$$$。

Tokitsukaze 想知道将序列中的所有数字更改为 $$$0$$$ 所需的最少操作次数。可以证明答案总是存在的。

输入

第一行包含一个正整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) — 序列 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 100$$$) — 序列 $$$a$$$。

输出

对于每个测试用例,打印一个整数 - 将序列中的所有数字更改为 $$$0$$$ 的最少操作数。

示例

输入 #1

3
3
1 2 3
3
1 2 2
3
1 2 0

输出 #1

4
3
2

注意

在第一个测试用例中,将序列中的所有数字更改为 $$$0$$$ 的可能方法之一:

在$$$1$$$-st运算中,$$$a_1 < a_2$$$,运算后,$$$a_2 = a_1 = 1$$$。现在序列 $$$a$$$ 是 $$$[1,1,3]$$$。

在第$$$2$$$次运算中,$$$a_1 = a_2 = 1$$$,运算后,$$$a_1 = 0$$$。现在序列 $$$a$$$ 是 $$$[0,1,3]$$$。

在$$$3$$$-rd运算中,$$$a_1 < a_2$$$,运算后,$$$a_2 = 0$$$。现在序列 $$$a$$$ 是 $$$[0,0,3]$$$。

在第 $$$4$$$ 次运算中,$$$a_2 < a_3$$$,运算后,$$$a_3 = 0$$$。现在序列 $$$a$$$ 是 $$$[0,0,0]$$$。

所以最小操作数是$$$4$$$。