解题思路
给定数组 a1,a2,…,an。对任意区间 [l,r] (1≤l<r≤n)，其贡献定义为区间内部所有下标 i（l<i<r）中满足
ai<al或ai<ar
的个数。要求所有区间贡献之和。
P3885.第4题-小小的区间
题目内容
给定一个长度为 n 的整数数组 {a1,a2,...,an}。对任意区间 [l,r] (满足 1≤l<r≤n )，定义其贡献为所有满足 l<i<r 且 (ai<al) 或 (ai<ar) 的下标 i 的个数。请你计算所有区间的贡献之和。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤2×105) 代表数据组数。
每组测试数据描述如下：
-
第一行输入一个整数 n(1≤n≤2×105) ，表示数组的长度；
-
第二行输入 n 个整数 a1,a2,...,an(1≦ai≦109) ，表示数组的元素。
除此之外，保证单个测试文件的 n 之和不超过 2×105 。
输出描述
对于每组测试数据，新起一行输出一个整数，表示答案。
样例1
输入
2
3
2 1 3
4
3 2 2 3
输出
1
4
说明
对第一组数据：n=3,a= {2,1,3}。
