题目

• 小龙虾有一个由 n 个正整数组成的序列 {a₁, a₂,..., aₙ}，其中 $2 ≤ n ≤ 10^5$ 且 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\%$的数据，$2 \le n \le 1000$.

• 对于另外$100\%$的数据，$2 \le n \le 100000$.