### 问题描述

小夜在一次冒险中，发现了一个神秘的宝石阵列，这个阵列包含 $N$ 个宝石，每个宝石都发出一个非负的能量值。小夜发现，如果选择阵列中的连续三个或更多个宝石进行激活，就能释放出一个强大的能量场。

一个宝石子阵列的能量定义为所有可能的三元组 $(i,j,k)$ 使得 $(B_i - B_j) \times (B_j - B_k)$ 的最大值，其中 $1≤i,j,k≤M$ 且 $i≠j≠k$。

现在，小夜想要知道，如果激活所有长度至少为 $3$ 的连续宝石子阵列，那么这些子阵列的能量之和是多少。

输入格式

第一行输入一个整数 $T$，表示测试用例的数量。

每个测试用例包含两行，第一行包含一个整数 $N$，表示宝石阵列的长度。第二行包含 $N$ 个空格分隔的整数，表示每个宝石的能量值。

输出格式

对于每个测试用例，输出一行，表示所有长度至少为3的连续宝石子阵列的能量之和。

输入样例

2
4
1 2 3 4
5
1 42 69 228 2021 

输出样例

4
1041808

评测数据范围

$1 \leq T\leq10$。

$3 \leq N \leq 3000$。

$1 \leq A_1 \leq A_i \leq \cdots A_n \leq 10^6$。

所有测试用例中 $N$ 的总和不超过 $6000$。