Little Cyan Fish 正在参加由 B 教授讲授的名为“Big-God-Live-Class”的在线竞赛编程课程。在最近的一节课中，B 教授介绍了一种使用两个优先队列寻找序列中位数的方法。受此启发，Little Cyan Fish 决定将其实现以进行练习。

具体来说，Little Cyan Fish 编写了一个程序，从输入文件中读取一个长度为 $n$ 的排列 $p_1, p_2, \dots, p_n$。该程序的目标是计算所有连续子序列 $p_l, p_{l+1}, \dots, p_r$（对于每个 $1 \le l \le r \le n$）的中位数之和。

为了测试他的程序是否正确，Little Cyan Fish 想要均匀地生成一个 $1, 2, \dots, n$ 的随机排列，并计算该和。他计划将他的程序计算出的和与正确答案进行比较。现在，你的任务是帮助他找到正确答案。

回想一下，数字列表 $a_1, a_2, \dots, a_t$ 的中位数定义为列表中第 $\lfloor \frac{t}{2} \rfloor$ 小的数（注：此处原文定义为 $\lfloor \frac{t}{2} \rfloor$ 小，根据样例推断，对于长度为 $t$ 的序列，中位数下标应为 $\lfloor \frac{t}{2} \rfloor + 1$ 或根据题目具体定义，请参考样例说明）。例如，$[1, 5, 4]$ 的中位数是 $4$，$[11, 4, 5, 14]$ 的中位数是 $5$。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3 \times 10^5$)。

下一行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)，表示该排列。保证 $p$ 是通过均匀选择 $n!$ 种排列之一生成的（由伪随机数生成器生成）。

最多有 $20$ 个测试文件。（注意，每个测试文件仅包含如上所述的单个测试用例。）

输出格式

输出一行，包含一个整数，表示答案。

样例

输入 1

4
1 4 2 3

输出 1

22

说明

• $[p_1] = [1]$ 的中位数是 $1$。
• $[p_2] = [4]$ 的中位数是 $4$。
• $[p_3] = [2]$ 的中位数是 $2$。
• $[p_4] = [3]$ 的中位数是 $3$。
• $[p_1, p_2] = [1, 4]$ 的中位数是 $1$。
• $[p_2, p_3] = [4, 2]$ 的中位数是 $2$。
• $[p_3, p_4] = [2, 3]$ 的中位数是 $2$。
• $[p_1, p_2, p_3] = [1, 4, 2]$ 的中位数是 $2$。
• $[p_2, p_3, p_4] = [4, 2, 3]$ 的中位数是 $3$。
• $[p_1, p_2, p_3, p_4] = [1, 4, 2, 3]$ 的中位数是 $2$。

因此，答案等于 $1 + 4 + 2 + 3 + 1 + 2 + 2 + 2 + 3 + 2 = 22$。