有$$$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$$$ 总和没有限制。
输出
对于每个测试用例,输出一个整数,表示您可以吃的最大苹果数。
示例
输入复制
342 2 2 251 4 5 1 265 4 2 1 2 3
输出复制
145
注意
在第一个测试用例中,由于所有苹果都具有相同的美感,因此无论您先吃哪个苹果,都不能再吃其他苹果。因此,您最多可以吃掉 $$$1$$$ 的苹果。
在第二个测试用例中,您可以吃四个苹果,如下所示:
- 在树 $$$1$$$ 处,跳过苹果。
- 在树 $$$2$$$ 处,跳过苹果。
- 在树 $$$3$$$ 处,跳过苹果。
- 在树$$$4$$$处,吃苹果(美女$$$1$$$)。
- 在树$$$5$$$处,吃苹果(美女$$$2$$$)。
- 在树 $$$1$$$ 处,跳过苹果。你不可以吃这个苹果,因为它的美丽度 ($$$b_1 = 1$$$) 不大于你上次吃的苹果的美丽度 ($$$b_5 = 2$$$)。
- 在树$$$2$$$处,吃苹果(美女$$$4$$$)。
- 在树$$$3$$$处,吃苹果(美女$$$5$$$)。
可以证明五个苹果不可能全部吃完;因此,您最多可以吃掉 $$$4$$$ 的苹果。