小龙虾有一个由 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