当前没有测试数据。

题目描述

蜗蜗有一条精美的珠串，上面串着$n$颗珠子。第$i$颗珠子的颜色编号为$a_i$。

现在蜗蜗对满足以下条件的珠子三元组 $(i,j,k)$ 非常感兴趣：

• 1.$1≤i,j,k≤n$。

• 2.珠子颜色编号满足关系:$|a_i-a_k|=|i−j|+|j−k|$。

请你帮蜗蜗计算，满足上述条件的三元组 $(i,j,k)$ 共有多少个？

你需要回答 $q$ 组独立的查询。

输入格式

第一行输入一个整数 $q$，表示查询的数量。

每组查询包括两行。

查询的第一行包含一个整数 $n$，表示珠子的数量。

查询的第二行包含 $n$ 个整数 $a_1,a_2...a_n$，表示每颗珠子的颜色编号。

输出格式

对于每组查询，输出一行一个整数，表示满足条件的三元组数量。

样例

1
3
1 2 3

17

样例解释

在第 $1$ 组查询中，$a=[1,2,3]$

当$i=k$时，只有 $j=i$ 满足条件，因此有 $(1,1,1),(2,2,2),(3,3,3)$，共 $3$ 个三元组。

当 $i≠k$时，若 $i$和 $k$ 分别为 $1,2$，则 ∣a_i−a_k∣=1满足条件的 $j$ 有 $1,2$ 两种；有序对 $(1,2)$ 和 $(2,1)$ 共贡献 $4$ 个三元组。同理，有序对 $(2,3)$ 和 $(3,2)$ 共贡献 $4$ 个三元组。

若 $i$和 $k$ 分别为 $1,3$，则 $∣a_i−a_k∣=2$，满足条件的 $j$ 有 $1,2,3$ 三种；有序对 $(1,3)$ 和 $(3,1)$ 共贡献 $6$ 个三元组。

所以答案为 $3+4+4+6=17$。

数据范围

对于 $30$ 的数据，保证 $1≤n≤500$。

对于另外 $30$ 的数据，保证 $1≤n≤2000$。

对于 $100$ 的数据，保证 $1≤q≤10,1≤n≤2×10^5,1≤a_i$