对于一个长度为 m 的非负整数序列 a1,…,am,考虑 m 行的棋盘,其中第 i 行有 ai 列。若存在一种用 1×2 和 2×1 的多米诺骨牌覆盖整个棋盘的方式,则称序列 a 是好的。
给出一个长度为 n 的非负整数序列 b1,…,bn,求有多少个 (l,r) 满足 1≤l≤r≤n 且 bl,…,br 可以被删空。
输入格式
第一行一个正整数 T,表示测试数据组数。
接下来对于每组数据,输入两行:
第一行一个正整数 n。
第二行 n 个非负整数 b1,…,bn。
输出格式
对于每组数据,输出一行一个非负整数,表示答案。
样例
样例 1 输入
9 5 5 6 6 5 3 9 3 7 1 8 4 4 0 6 9 3 3 1 0 3 3 0 1 3 2 0 2 1 0 10 4 7 6 6 7 6 1 2 5 5 6 5 5 5 4 3 3 6 6 4 4 6 4 1
样例 1 输出
7 22 3 1 6 1 12 7 15
样例 1 说明
对于第一组数据,b=[5,6,6,5,3],合法的 (l,r) 有:(2,2),(3,3),(2,3),(4,5),(3,5),(1,4),(2,5)。
样例 2
见下发文件。
数据范围
对于所有数据,满足 1≤T≤100,1≤n≤5×105,∑n≤106,0≤bi≤109。
- subtask 1(5%):n≤10。
- subtask 2(20%):n≤100,∑n≤5×103。
- subtask 3(20%):∑n≤5×103。
- subtask 4(20%):∑n≤105。
- subtask 5(35%):无特殊限制。