小H算数

题号：NC284898
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小 H 是哪个角色？小 H 自己也不知道，但小 H 已经学会弹标题以 H 开头的一首歌了，望周知。

$\hspace{15pt}$ 小 H 有一个由 $n$ 个正整数组成的序列 $\{a_1,a_2,...,a_n\}$ ，对于其全部的区间 $[i,j] \left(1 \le i<j \le n\right)$ ，定义函数 $c(i,j)$ 和 $d(i,j)$ 如下：
$\hspace{15pt}$ 下面是函数 $c$ 的定义：
$\hspace{23pt}\bullet\,$ 若 $a_i=a_j$ ，则 $c(i,j)$ 等于区间中比两端（即 $a_i$ ）大的元素个数；
$\hspace{23pt}\bullet\,$ 若 $a_i \neq a_j$ ，则 $c(i,j) = 0$ 。
$\hspace{15pt}$ 下面是函数 $d$ 的定义：
$\hspace{23pt}\bullet\,$ 若区间长度（即 $j-i+1$ ）是奇数，则 $d(i,j)=1$ ；
$\hspace{23pt}\bullet\,$ 若区间长度（即 $j-i+1$ ）是偶数，则 $d(i,j)=2$ 。
$\hspace{15pt}$ 你需要帮小 H 求出序列 $a$ 中所有区间的 $c(i,j) \times d(i,j)$ 之和。

输入描述:

第一行输入一个整数  代表序列中的元素个数。 
第二行输入  个整数  代表序列中的元素。

输出描述:

在一行上输出一个整数，代表所有  之和。

示例1

输入

复制

6
1 1 4 5 1 4

输出

复制

说明

在这个样例中，除  ，其余  均为  。
故我们只关心非  的  ，即 。
最终，计算答案是  。