#P18622. Triterminant
Triterminant
Triterminant
对于整数序列 ,定义多项式 :
$$A_k(x)=\det\begin{pmatrix} x&b_1&0&\cdots&0\\ 1&x&b_2&\ddots&\vdots\\ 0&1&x&\ddots&0\\ \vdots&\ddots&\ddots&\ddots&b_k\\ 0&\cdots&0&1&x \end{pmatrix}.$$矩阵大小为 。更准确地说,主对角线元素均为 ,第 个上对角线元素为 ,第 个下对角线元素为 (),其余元素为 。
如果对所有 , 的每个系数的绝对值都不超过 ,则称序列 是好序列。
给定序列 ,其中每项都是 或 。你可以选择任意若干项,将其符号翻转,即将 改为 。求使序列变为好序列,至少需要改变多少项。
输入格式
输入包含多组测试数据。
第一行包含测试数据组数 ,其中 。
每组测试数据的第一行包含整数 ,其中 。
第二行包含 个整数 ,其中 。
保证所有测试数据的 之和不超过 。
输出格式
对每组测试数据,输出一个整数,表示最少需要改变的元素个数。
如果不存在任何方案能将给定序列变为好序列,则输出 。
样例输入 1
3
4
1 1 1 1
2
1 -1
5
-1 1 1 1 -1
样例输出 1
2
0
2
样例说明
是一个好序列,可以从 改变两项得到。