题目内容

小 A 面前摆放着一排编号为 $1$ 到 $n$ 的盒子，第 $i$ 个盒子中有 $a_i$ 枚金币。这些盒子按照位置交替被涂成红色和蓝色：位置 $1$ 的盒子是红色，位置 $2$ 是蓝色，位置 $3$ 又是红色……如此交替。

对于一段连续的盒子 $[l, r]$（$1 \le l \le r \le n$），我们定义蓝色盒子的金币总和减去红色盒子的金币总和为该区间的「净收益」。如果某个区间的净收益大于 $0$，则小 A 称这段区间为「优质区间」。请帮助小 A 计算一共有多少个优质区间。

可以存在多组测试数据。数据规模保证：测试数据组数 $T$ 满足 $1 \le T \le 10^4$。对于每组数据，数组长度 $n$ 满足 $1 \le n \le 2 \times 10^5$，且所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。每个盒子的金币数 $a_i$ 满足 $1 \le a_i \le 10^9$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。