logo AlgoBeat OnlineJudge
登录 注册

#103152. [BZOJ 3152] [Ctsc2013]组合子逻辑

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

组合子逻辑是 Moses Schönfinkel 和 Haskell Curry 发明的一种符号系统,用于消除数理逻辑中对于变量的需要。本题考察一种与真实世界的组合子演算略有差别的组合子系统。

一个组合子项是下列形式之一:

其中 表示一个基本函数, 以及 表示一个组合子项(可以相同)。不满足以上形式表达式均非组合子项。

我们将一个组合子项 的参数个数 如下:

基本函数 的参数个数;

本题中,我们用一个正整数同时表示一个基本函数,以及该基本函数的参数个数。

对于一个组合子项 ,如果它和它包含的所有组合子项的参数个数 均为正整数,那么我们称这个 为范式。

我们经常组合子项简化表示:如果一个组合子项EE含有连续子序列 (其中 ),其中 表示组合子项(可以是简化表示的),那么将该部分替换为 ,其他部分不变,得到表达式 的一个简化表示。一个组合子项可以被简化表示多次。

给定一个基本函数序列,问至少需要添加多少对括号,才能使得该表达式成为一个范式的简化表示(即满足范式的性质);如果无论如何怎样添加括号,均不能得到范式的简化表示,输出

输入格式

第一行包含一个正整数 ,表示有 次询问。

接下来 行。

行有一个正整数 ,表示第 次询问的序列中基本函数的个数。

行有 个正整数,其中第 个整数表示序列中第 个基本函数。

输出格式

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

样例输入

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

样例输出

3
-1

样例说明

第一次询问:一个最优方案是 。可以证明不存在添加括号对数更少的方案。

第二次询问:容易证明不存在合法方案。

数据范围与提示

表示输入中所有 的和。