← 返回题目列表

Codeforces · 2200/B

B. 删除排序

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

AksLolCoding 正在 $$$a$$$ 的 $$$n$$$ 正整数数组上玩游戏。在每个回合中:

  • 如果 $$$a$$$ 是 非递减$$$^{\text{*}}$$$,游戏结束。
  • 否则,AksLolCoding可以选择 任何 单个元素并将其从数组中删除。

确定 最小值 游戏结束后数组中可能保留的元素数量。

如果对于所有 $$$1\leq i\leq m-1$$$,$$$a_i\leq a_{i+1}$$$ 是非递减的,其中 $$$m$$$ 是 $$$a$$$ 的长度。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数,即 $$$a$$$ 的元素 ($$$1 \leq a_i \leq 100$$$)。

输出

对于每个测试用例,输出一个整数:数组排序后剩余的最小可能元素数。

示例

输入
复制

3
4
1 4 2 3
1
100
2
6 7

输出
复制

1
1
2

注意

在第一个测试用例中,可以通过按顺序删除 $$$1$$$、$$$2$$$ 和 $$$3$$$ 来实现 $$$1$$$ 元素的最小值。

在第二个和第三个测试用例中,无法删除任何元素。