制作三角形

题目描述

有 $N$ 根编号为 $1, \cdots, N$ 的棒。棒 $i$ $(1 \leq i \leq N)$ 的长度为 $L_i$。

从中选出长度互不相同且能组成三角形的 $3$ 根棒,有多少种选法?

也就是说,求满足以下两个条件的三元组 $1 \leq i \lt j \lt k \leq N$ 的个数:

• $L_i, L_j, L_k$ 全部互不相同
• 存在边长分别为 $L_i, L_j, L_k$ 的三角形

输入格式

输入按以下格式从标准输入给出:

$N$
$L_1$ $L_2$ $\cdots$ $L_N$

输出格式

输出能组成三角形的长度互不相同的 $3$ 根棒的选择方法数。

样例

5
4 4 9 7 5

5

满足条件的 $(i, j, k)$ 有 $(1, 3, 4), (1, 4, 5), (2, 3, 4), (2, 4, 5), (3, 4, 5)$,共 $5$ 个。

6
4 5 4 3 3 5

8

长度为 $3, 4, 5$ 的棒各有 $2$ 根。为了满足第 $1$ 个条件,只能每种长度各选 $1$ 根。

由于存在边长为 $3, 4, 5$ 的三角形,满足条件的 $(i, j, k)$ 有 $2 ^ 3 = 8$ 个。

10
9 4 6 1 9 6 10 6 6 8

39

2
1 1

0

因为不存在满足 $1 \leq i \lt j \lt k \leq N$ 的 $(i, j, k)$,输出 $0$。

数据范围

• $1 \leq N \leq 100$
• $1 \leq L_i \leq 10^9$
• 输入均为整数