思路

1. 问题转化 题目的核心条件是 $\text{even}(l, r) > \text{odd}(l, r)$。我们可以将这个不等式进行移项，得到： $\text{even}(l, r) - \text{odd}(l, r) > 0$ 这个形式启发我们去构造一个新的数组，使得新数组的区间和恰好等于 $\text{even}(l, r) - \text{odd}(l, r)$。

2. 构造新数组与前缀和 我们可以定义一个新数组 $c$，其元素 $c_i$ 的值与原数组 $a_i$ 的奇偶性有关：

题目内容

给定一个长度为 $n$ 的正整数数组 {$a_1,a_2,...,a_n$}，下标从 $1$ 开始计数。

我们把区间 $[l,r](1≦l≦r≦n)$ 中全局下标为偶数的位置上的元素之和记为 $even(l,r)$ ，把区间内全局下标为奇数的位等上的元素之和记为 $odd(l,r)$ 。

现在，Tk 想知道有多少个区间 $[l,r]$ 满足

$even(l,r)＞odd(l,r)$ 。

输入描述

每个测试文件包含多组测试数据。

第一行输入一个整数 $T(1 ≤T≤ 10^4)$ 代表数据组数，每组测试数据描述如下：

除此之外，保证单个测试文件的 $n$ 之和不超过 $2 × 10^5$ 。

• 第一行输入一个整数 $n(1≤n≤2×10^5)$ ，代表数组长度；

• 第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≤a_i≤10^9)$ 代表数组元素。

输出描述

对于每一组测试数据，在一行上输出一个整数，表示满足 $even(l,r)＞odd(l,r)$ 的区间数量。

样例1

输入

1
4
1 3 2 2

输出

6

说明

解释：数组为 {$1,3,2,2$} 。满足条件的区间共有 $6$ 个，具体如下：

• $[2,2]$，偶数下标元素和为 $3$，奇数下标元素和为 $0$ ；

• $[4,4]$，偶数下标元素和为 $2$，奇数下标元素和为 $0$ ；

• $[1,2]$，偶数下标元素和为 $3$，奇数下标元素和为 $1$ ；

• $[1,4]$，偶数下标元素和 $3+2=5$ ，奇数下标元素和为 $1+2=3$ ；

• $[2,3]$，偶数下标元素和为 $3$ ，奇数下标元素和为 $2$ ；

• $[2,4]$，偶数下标元素和为 $3+2=5$ ，奇数下标元素和为 $2$ 。