题目描述

给定一个长度为 $n$ 的序列 $\{a_n\}$，求其所有非空连续子序列的中位数的和。

对于长度为 $n$ 的序列 $\{b_n\}$，将其非严格降序排序后得到 $\{c_n\}$，那么 $c_{\lceil \frac n2\rceil}$ 是它的中位数。例如，$1,2,3$ 和 $1,2$ 的中位数都是 $2$。

输入格式

第一行一个整数 $n$，表示序列的长度。

第二行 $n$ 个整数，其中第 $i$ 个整数为 $a_i$。

输出格式

一个整数，表示答案。

3
3 1 2

13

20
626693109 804150259 779008573 895258084 747539895 626693109 16565603 915520313 747539895 626693109 747539895 804150259 779008573 184688841 804150259 16565603 60347795 915520313 16565603 915520313

148049168955

样例解释

$[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]$ 中位数分别为 $3,3,2,1,2,2$，和为 $13$。

数据规模与约定

• 对于 $20\%$ 的数据，$n\le 100$。
• 对于 $40\%$ 的数据，$n\le 2000$。
• 对于另外 $30\%$ 的数据，$\{a_n\}$ 是一个排列。
• 对于 $100\%$ 的数据，$1\le n\le 7000$，$1\le a_i\le 10^9$。