CFCF2165F.Arctic Acquisition

给定一个长度为 $n$ 的排列 $a_1,a_2,\ldots,a_n$。

对于一个区间 $[l,r]$（$1\le l\le r\le n$），如果它包含一个 21435 子序列，则称其为一个“jagged”区间；也就是说，存在整数 $i_1,i_2,i_3,i_4,i_5$，使得 $l\le i_1<i_2<i_3<i_4<i_5\le r$，并且 $a_{i_2}<a_{i_1}<a_{i_4}<a_{i_3}<a_{i_5}$。

你的任务是计算在 $\frac{n(n+1)}{2}$ 个区间中，有多少个区间是 “jagged” 的。

附：排列指的是长度为 $n$ 的数组，包含 $1$ 到 $n$ 的 $n$ 个互不相同的整数，顺序任意。例如 $[2,3,1,5,4]$ 是一个排列，但是 $[1,2,2]$ 不是（$2$ 出现两次），$[1,3,4]$ 也不是（$n=3$，但数组中有 $4$）。

每组测试包含若干个测试用例。第一行为测试用例的数量 $t$（$1 \le t \le 10^4$）。每组测试用例描述如下。

每组测试用例第一行包含一个整数 $n$（$1\le n\le10^6$），表示排列的长度。

第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le n$）。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每组测试用例，输出 jagged 区间的个数。

在第一个测试用例中，唯一的 jagged 区间是 $[1,5]$，因为它包含 $[2,1,4,3,5]$ 作为子序列。

在第三个测试用例中，区间 $[1,8]$ 是 jagged 的，因为它包含 $[9,6,11,10,13]$ 作为子序列，这就是一个 21435-子序列。