题目描述

有$n$位ACMer住在一条东西走向的街道上（可以将街道看作一条线段）。

每位ACmer拥有一个独一无二的竞赛积分（Rating）。为了提高自己的实力、早日变成算法高手，他们经常一起vp一起切磋。如果两位ACmer想要进行切磋，他们必须从其他ACMer中选择一位作为裁判，并且比赛要在裁判的家中举行。出于某些原因，切磋的两位ACmer不能选择一个Rating比他们两人都高或者都低的裁判。

两位ACmer需要步行到裁判家中，出于贪心策略（其实就是懒），他们希望总步行距离不超过两人住址之间的距离。当然，每位ACmer住的位置互不相同。

如果裁判或者任意一位参赛的ACmer不同，则认为是两场不同的比赛。

那在这条ACM街上，一共可以举办多少场不同的比赛？

输入格式

第一行包含一个整数$T(1 \le T \le 20)$，测试用例的数量。
每组测试用例包含$n + 1$个整数：第一个整数为$n(1 \le n \le 10^5)$，这条街上ACmer的数量，接下来$n$个整数$a_1,a_2 ,..., a_n( 1\le a_i \le 10^5)$，表示从西到东每位ACmer的Rating。

输出格式

对于每个测试用例，输出一行一个整数，表示不同比赛的数量。

样例

1
3 1 2 3

1

提示

这条街上只能举行一场比赛：第2位ACMer和第4位ACMer在第3位ACMer的家中比赛。