← 返回题目列表

Codeforces · 1616/C

C. 代表性边缘

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

数组 $$$a_1, a_2, \ldots, a_n$$$ 是好的,当且仅当对于每个子段 $$$1 \leq l \leq r \leq n$$$,以下成立: $$$a_l + a_{l + 1} + \ldots + a_r = \frac{1}{2}(a_l + a_r) \cdot (r - l + 1)$$$。

给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。在一次操作中,您可以将此数组的任何一个元素替换为任何实数。求出使该数组正常运行所需的最少操作数。

输入

第一行输入包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$):测试用例的数量。

接下来的 $$$t$$$ 行包含测试用例的描述。

在第一行中,您将获得一个整数 $$$n$$$ ($$$1 \leq n \leq 70$$$):数组中整数的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-100 \leq a_i \leq 100$$$):初始数组。

输出

对于每个测试用例,打印一个整数:为使给定数组正常运行而需要替换的最小元素数。

示例

输入 #1

5
4
1 2 3 4
4
1 1 2 2
2
0 -1
6
3 -2 4 -1 -4 0
1
-100

输出 #1

0
2
0
3
0

注意

在第一个测试用例中,数组已经很好了。

在第二个测试用例中,可能的好数组之一是 $$$[1, 1, \underline{1}, \underline{1}]$$$ (替换的元素带有下划线)。

在第三个测试用例中,数组已经很好了。

在第四个测试用例中,可能的好数组之一是 $$$[\underline{-2.5}, -2, \underline{-1.5}, -1, \underline{-0.5}, 0]$$$。