题目描述

本题中，你需要解决一个著名的 NP 问题——保序回归问题。

保序回归问题要有变量：你需要给出一个长度为 $n$ 的整数序列 $(x_1,x_2,\ldots,x_n)$，满足下文中的所有条件。

保序回归问题要有约束：一般的保序回归问题需要保持偏序，但这样就成板子题了，所以在本题中你只需要保证 $\prod_{i=1}^n x_i>0$。

保序回归问题要有目标函数：也就是回归代价，和其它 $L_1$ 保序回归问题一样，在给出 $n$ 个整目标参数 $y_1,y_2,\ldots,y_n$ 的前提下，你需要最小化 $\sum_{i=1}^n |x_i-y_i|$。

保序回归问题不一定要有多组询问，本题也没有，但是每个测试点包含有多组测试数据。

输入格式

第一行包括一个整数 $T$，代表测试数据组数。

接下来依次读入 $T$ 组测试数据，对于每组测试数据：

• 第一行包括一个整数 $n$。
• 第二行包括 $n$ 个用空格分隔开的整数，依次为 $y_1,y_2,\ldots y_n$。

输出格式

共 $T$ 行，每行一个整数，依次代表每组测试数据的答案。

样例

样例输入 1

3
3
-3 -2 -2
9
9 9 8 2 4 4 3 5 3
3
0 0 0

样例输出 1

3
0
3

样例解释 1

对于第一组测试数据，一种满足条件的 $(x_1,x_2,x_3)$ 为 $(-3,1,-2)$。其满足 $\prod_{i=1}^n x_i=(-3)\times 1\times (-2)=6>0$，其回归代价为 $\sum_{i=1}^n|x_i-y_i|=|(-3)-(-3)|+|1-(-2)|+|(-2)-(-2)|=3$。可以证明没有回归代价 $<3$ 的合法序列，故答案为 $3$。

对于第三组测试数据，一种满足条件的序列为 $(1,-1,-1)$。

样例输入 / 输出 2

见下发文件中的 ex_isoreg2.in/ex_isoreg2.ans。

数据范围

本题共有 $10$ 个测试点，每个测试点 $10$ 分。

记 $\sum n$ 为某个测试点中所有测试数据的 $n$ 之和。

对于所有测试点，保证 $1\le T,n,\sum n\le 2\times10^5,-10^9\le y_i\le 10^9$。

对于测试点 $1$，保证 $T,n,|y_i|\le 5$。

对于测试点 $2,3$，保证 $\sum n,|y_i|\le 100$。

对于测试点 $4,5$，保证 $\sum n,|y_i|\le 1000$。

对于测试点 $6$，保证对于每组测试数据，$\prod_{i=1}^n y_i\ne 0$。

对于测试点 $7$，保证对于每组测试数据，$\prod_{i=1}^n y_i=0$。

对于测试点 $8,9,10$，无特殊限制。