本题目满分 150 分。

题目描述

你有一个 $n$ 项序列 $a_1,a_2,\ldots,a_n$，计算有多少个五元子序列，存在一组 $y,u,m$ 使这个子序列恰为 $y,u,m,m,y$。

注意两个子序列不同当且仅当存在元素位置不同。

输入格式

第一行有一个正整数 $n$ 表示序列元素数。

第二行有 $n$ 个正整数 $a_1,a_2,\ldots,a_n$ 表示这个序列。

输出格式

输出一行一个自然数表示答案。由于子序列可能过多，你只需要求子序列个数除以 $2^{32}$ 的余数即可。

样例 #1

样例输入 #1

8
1 2 2 2 4 4 1 2

样例输出 #1

7

提示

【样例解释】

• 令 $y=1,u=m=2$，可以找到 $1$ 个子序列 $[1,2,2,2,1]$。
• 令 $y=1,u=2,m=4$，可以找到 $3$ 个子序列 $[1,2,4,4,1]$。
• 令 $y=u=2, m=4$，可以找到 $3$ 个子序列 $[2,2,4,4,2]$。

【数据范围】

对于全部数据，保证 $5\le n\le 2\times 10^5$，$1\le a_i\le 2\times 10^5$。