对于整数数组[a1,a2,…,an]，我们称之为价值|a1−a2|+|a2−a3|+⋯+|an−1−an|这对比数组的。注意数组大小的对比1等于0. 给你一个整数数组a。你的任务是建立一个数组b满足以下所有条件: b不为空，即至少有一个元素； b是的子序列a，即b可以通过从中删除一些元素来产生a(可能是零)； 的对比b等于的对比a. 阵列的最小可能大小是多少b? 投入 第一行包含一个整数t (1≤t≤104)—测试用例的数量。 每个测试用例的第一行包含一个整数n (1≤n≤3⋅105)—数组的大小a. 第二行包含n整数a1,a2,⋅,an (0≤ai≤109)—数组本身的元素。 的总和n所有测试案例不超过3⋅105. c++shixna

题目大意：

给定一个长度为n的整数数组a，定义数组的价值为|a1−a2|+|a2−a3|+⋯+|an−1−an|。

现在要构建一个非空子序列b，使得b的价值等于a的价值，求b的最小长度。

思路：

我们可以发现，题目中的价值实际上是相邻元素差的绝对值之和，也就是说，价值只与元素差的绝对值有关，而与元素值的大小无关。因此我们可以对a数组进行排序，然后考虑在排序之后的数组中构建子序列b。

我们可以从排序后的数组中选择若干个元素，使得它们依次相邻，即可以形成一个子序列。对于这个子序列的价值，我们可以通过计算每个相邻元素差的绝对值之和得到。我们可以通过遍历整个排序后的数组，来找到所有能够构建的子序列中价值最小的那一个，其长度就是我们要求的b的最小长度。

具体地，我们可以使用两个指针i和j，分别指向排序后的数组的第一个元素和第二个元素。然后不断地将j向右移动，直到找到一个位置，使得从i到j的这个子序列的价值等于a数组的价值为止。然后我们可以记录下这个子序列的长度，然后将i向右移动一个位置，继续寻找下一个子序列。最终我们可以得到所有能够构建的子序列中长度最小的那一个，其长度就是我们要求的b的最小长度。

代码实现：