问题描述

一个长度至少为 $2$ 的数组 $b$ 的连续子数组，若其首尾元素都是 $1$，且中间所有元素都是 $0$，则称它为一个满足条件的子数组。$b$ 的得分定义为所有满足条件的子数组中的最大长度。

形式化地，得分是最大的整数 $k$（$k\geq2$），使得存在一个长度为 $k$ 的子数组，其首尾元素为 $1$，其余元素为 $0$。不存在这样的子数组时，得分为 $0$。

给定一个数组 $a_1,a_2,\ldots,a_n$，其中每个元素是 $-1$、$0$ 或 $1$。你可以把每个 $-1$ 替换成 $0$ 或 $1$。

请输出替换后数组能够取得的最大得分。

输入格式

第一行输入一个整数 $t$，表示测试用例数量。

对于每个测试用例：

• 第一行输入一个整数 $n$，表示数组长度；
• 第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示数组 $a$。

输出格式

对于每个测试用例，输出一行一个整数，表示替换后数组可以取得的最大得分。

样例输入 1

10
6
1 0 -1 0 0 1
7
0 -1 0 0 1 0 1
5
-1 0 0 -1 0
4
0 0 0 0
1
-1
6
1 0 1 0 0 -1
7
0 1 0 0 0 1 0
6
-1 -1 -1 -1 -1 -1
7
-1 0 1 -1 0 0 1
3
-1 0 0

样例输出 1

6
4
4
0
0
4
5
6
5
0

样例解释 1

第一个测试用例可以把唯一的 $-1$ 替换为 $0$，得到 $[1,0,0,0,0,1]$，得分为 $6$。

第十个测试用例中，无论怎样替换，数组中都无法出现两个作为首尾的 $1$，因此得分为 $0$。

评测数据规模

对于所有数据，保证：

• $1\leq t\leq10000$；
• $1\leq n\leq2\times10^5$；
• $a_i\in\{-1,0,1\}$；
• 每个输入文件中所有测试用例的 $n$ 之和不超过 $2\times10^5$。