小龙虾有一个由 n 个正整数组成的序列 {a₁, a₂,..., aₙ}，其中 2 ≤ n ≤ 10⁶ 且 1 ≤ aᵢ ≤ n。

对于序列的所有区间 [i, j]（1 ≤ i < j ≤ n），定义两个函数 c(i, j) 和 d(i, j)：

c(i, j) 的定义：

若 aᵢ = aⱼ，则 c(i, j) 等于区间 [i, j] 中比两端（即 aᵢ）大的元素的个数。 若 aᵢ ≠ aⱼ，则 c(i, j) = 0。

d(i, j) 的定义： 若区间 [i, j] 的长度（即 j - i + 1）是奇数，则 d(i, j) = 1。 若区间 [i, j] 的长度是偶数，则 d(i, j) = 2。 要求计算序列 a 中所有区间的 c(i, j) × d(i, j) 之和。

输入描述 第一行输入一个整数 n，表示序列中的元素个数。 第二行输入 n 个整数 a₁, a₂,..., aₙ，表示序列中的元素。

输出描述 在一行中输出一个整数，代表所有 c(i, j) × d(i, j) 之和。

示例 1 输入：

6 1 1 4 5 1 4

输出：

8

说明： 在这个样例中，除 c(1, 5) = 2、c(2, 5) = 2、c(3, 6) = 1 外，其余 c(i, j) 均为 0。 对于非零的 c(i, j)，d(1, 5) = 1、d(2, 5) = 2、d(3, 6) = 2。 最终计算结果为 2×1 + 2×2 + 1×2 = 8。

数据范围与提示

对于40%的数据，n ≤ 1000.

对于另外100%的数据，n ≤ 100000.