题目描述

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$。对于任意一段至少包含两个位置的区间 $[i,j]$，其中 $1\le i<j\le n$，定义两个量 $c(i,j)$ 与 $d(i,j)$。

若 $a_i=a_j$，则 $c(i,j)$ 等于区间内部位置 $i+1,i+2,\ldots,j-1$ 中，数值严格大于 $a_i$ 的元素个数；若 $a_i\ne a_j$，则 $c(i,j)=0$。

若区间长度 $j-i+1$ 为奇数，则 $d(i,j)=1$；若区间长度 $j-i+1$ 为偶数，则 $d(i,j)=2$。

请计算所有满足 $1\le i<j\le n$ 的区间对应的 $c(i,j)\times d(i,j)$ 之和。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示所有区间的贡献总和。

样例

8
2 5 2 4 2 5 1 2

16

样例说明

数据范围

• 对于 $30\%$ 的数据，$n\le 1000$。
• 对于 $100\%$ 的数据，$2\le n\le 10^6$，$1\le a_i\le n$。