← 返回题目列表

Codeforces · 2153/A

A. 苹果树圈

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

有$$$n$$$苹果树排列成一圈。每棵树只结一个苹果,第 $$$i$$$ 棵树上的苹果的美丽度由 $$$b_i$$$ 给出,对于所有 $$$1\le i\le n$$$。你从$$$1$$$树前开始。

在每棵树上,您可以选择吃苹果或不吃苹果。做出选择后,您将移至下一棵树:从 $$$i$$$ 树,您移至 $$$i+1$$$ 树 $$$1 \le i \le n - 1$$$,从 $$$n$$$ 树,您移回 $$$1$$$ 树。当您在树中循环移动时,这个过程会无限期地持续下去。

然而,你有一个特殊的条件:你只能吃一个苹果,如果它的美丽度严格大于你上次吃的苹果的美丽度。例如,如果 $$$b = [2, 1, 2, 3]$$$ 并且您吃了树上的苹果 $$$1$$$(美度 $$$2$$$),则您不能吃树上的苹果 $$$2$$$ 和 $$$3$$$,因为它们的美度不大于 $$$2$$$。然而,你可以吃掉 $$$4$$$ 树上的苹果,因为 $$$b_4 = 3 \gt 2$$$。

请注意,当你第一次遇到苹果时,你可以跳过它,并且你可以选择在后续循环中稍后吃它。

如果您就何时吃或不吃每个苹果做出最佳决定,您的任务是确定您可以吃的最大苹果数量。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n\le 100$$$) — 苹果树的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1\le b_i\le n$$$) — 树上苹果的美丽。

请注意,所有测试用例的 $$$n$$$ 总和没有限制。

输出

对于每个测试用例,输出一个整数,表示您可以吃的最大苹果数。

示例

输入
复制

3
4
2 2 2 2
5
1 4 5 1 2
6
5 4 2 1 2 3

输出
复制

1
4
5

注意

在第一个测试用例中,由于所有苹果都具有相同的美感,因此无论您先吃哪个苹果,都不能再吃其他苹果。因此,您最多可以吃掉 $$$1$$$ 的苹果。

在第二个测试用例中,您可以吃四个苹果,如下所示:

  • 在树 $$$1$$$ 处,跳过苹果。
  • 在树 $$$2$$$ 处,跳过苹果。
  • 在树 $$$3$$$ 处,跳过苹果。
  • 在树$$$4$$$处,吃苹果(美女$$$1$$$)。
  • 在树$$$5$$$处,吃苹果(美女$$$2$$$)。
  • 在树 $$$1$$$ 处,跳过苹果。你不可以吃这个苹果,因为它的美丽度 ($$$b_1 = 1$$$) 不大于你上次吃的苹果的美丽度 ($$$b_5 = 2$$$)。
  • 在树$$$2$$$处,吃苹果(美女$$$4$$$)。
  • 在树$$$3$$$处,吃苹果(美女$$$5$$$)。

可以证明五个苹果不可能全部吃完;因此,您最多可以吃掉 $$$4$$$ 的苹果。