F-小苯的数组计数_牛客周赛 Round 106

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯认为一个长度为 $m$ 的数组 $b_1,b_2,\dots,b_m$ 是美丽的，当且仅当其满足以下所有条件：
$\hspace{23pt}\bullet\,$ $m\geq 3$ ；
$\hspace{23pt}\bullet\,$ $b_1 \neq b_m$ ；
$\hspace{23pt}\bullet\,$ 对于任意 $1<i<m$ ，均有： $b_1> b_i$ 且 $b_i < b_m$ （即所有中间元素的数值都必须同时小于首位元素和末位元素）。

$\hspace{15pt}$ 现在小苯给定了一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$ ，他想知道 $a$ 中有多少个子数组是美丽的，请你帮他数一数吧。

【名词解释】
$\hspace{15pt}$ 子数组：从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 ，表示序列  的长度。
第二行  个整数 ，表示序列 。
除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示美丽子数组的个数。

示例1

输入

复制

2
5
1 3 2 1 3
8
4 3 2 1 5 6 7 8

输出

复制

1
3

说明

对于第一组测试数据，仅有  一个美丽数组。