思路

• 频次统计：设不同取值共有 $m$ 种，第 $i$ 种值的出现次数为 $n_i$。

• 组合计数：选择两种不同的值 $i\ne j$，从其中一种取 $3$ 个，另一种取 $2$ 个。对固定的 $(i,j)$，可行子序列数为 $\binom{n_i}{3}\binom{n_j}{2}$。对所有有序对求和，答案为

  

题目内容

小红定义一个长度为 $5$ 的数组是"葫芦”，当且仅当数组仅包含两种元素，其中一种出现次数为 $2$ ，另一种出现次数为 $3$ 。例如、{$1,1,4,1,4$} 是葫芦，而 {$1,2,3,4,5$}、{$6,6,6,6,6$} 均不是葫芦。

现在小红拿到了一个数组，她想知道有多少长度为 $5$ 的 子序列 是“葫芦”?

子序列 为从原数组中删除任意个(可以为零、可以为全部)元素得到的新数组。

输入描述

第一行输入一个正整数 $n(1≦n≦ 5000)$ ，代表数组的长度。

第二行输入 $n$ 个正整数 $a_1,a_2,...,a_n (1 ≦ a_i≦ 10^9)$ 代表数组的元素。

输出描述

输出一个整数，代表“葫芦”的数量。

样例1

输入

6
1 1 4 5 1 4

输出

1

样例2

输入

6
1 1 4 4 4 1

输出

6