#P12768. 中位数

    ID: 11954 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>CF1600枚举前缀和数学2025“钉耙编程”中国大学生算法设计暑期联赛(1)

中位数

中位数

Problem Description

对于一个长度为 LL (LL 为奇数) 的数组 aa,定义它的中位数 median\text{median}(a) 为 aa 中第 L+12\dfrac{L+1}2 大的数。 现在给你一个长度为 nn 的排列,对于每对满足 1≤i≤j≤n1\leq i\leq j\leq n 且 j−i≡0(mod2)j -i \equiv 0\pmod 2 的 (ii, jj),你需要计算 i∗j∗mediani*j * \text{median}(p[i…j]p[i\dots j])。 输出所有值的总和。

Input

第一行输入一个整数 TT (1≤T≤201 \le T \le 20),表示测试的总数。 对于每个测试用例,第一行输入一个整数 nn(1≤n≤20001 \le n \le 2000)。 接来下一行 nn 个整数,表示 11 到 nn 的排列。

Output

对于每个测试用例,输出一个数表示答案。

Sample Input

2
3
1 3 2
5
2 3 1 5 4

Sample Output

37
308

Source

2025“钉耙编程”中国大学生算法设计暑期联赛(1)