[Ctsc2013]组合子逻辑

时间限制:10s      空间限制:128MB

题目描述

组合子逻辑是Moses  SchönfinkelHaskell  Curry发明的一种符号系统,用于消除数理逻辑中对于变量的需要。本题考察一种与真实世界的组合子演算略有差别的组合子系统。 一个组合子项是下列形式之一:
P 
(E1 E2)
其中P表示一个基本函数,E1以及E2表示一个组合子项(可以相同)。不满足以上形式的表达式均非组合子项。
我们将一个组合子项E的参数个数np(E)如下:
np(P) =  基本函数P的参数个数;
np((E1 E2)) = np(E1) - 1
本题中,我们用一个正整数同时表示一个基本函数,以及该基本函数的参数个数。 对于一个组合子项E,如果它和它包含的所有组合子项的参数个数np均为正整数,那么我们称这个E为范式。
我们经常组合子项简化表示:如果一个组合子项E含有连续子序列( ((E1  E2)  E3)  … En) (其中n   3),其中Ek表示组合子项(可以是简化表示的),那么将该部分替换为(E1  E2 E3   En),其他部分不变,得到表达式E的一个简化表示。一个组合子项可以被简化表示多次。 给定一个基本函数序列,问至少需要添加多少对括号,才能使得该表达式成为一个范式的简化表示(即满足范式的性质);如果无论如何怎样添加括号,均不能得到范式的简化表示,输出-1


输入格式

    第一行包含一个正整数T,表示有T次询问。 接下来2T行。 2k行有一个正整数nk,表示第k次询问的序列中基本函数的个数。 2k + 1行有nk个正整数,其中第i个整数表示序列中第i个基本函数。


输出格式

 
输出T行,每行一个整数,表示对应询问的输出结果。


样例输入

2 
5 
3 2 1 3 2 
5 
1 1 1 1 1 

 

 

样例输出

3 
-1 

 

 

提示


【样例说明】
第一次询问:一个最优方案是(3 (2 1) (3 2))。可以证明不存在添加括号对数更少的方案。
第二次询问:容易证明不存在合法方案。

TN表示输入中所有nk的和。TN2000000


题目来源

没有写明来源