Making Triangle

题目描述

我们有编号为 $1, \cdots, N$ 的木棍。木棍 $i$ 的长度 $(1 \leq i \leq N)$ 为 $L_i$。 有多少种方法可以选择三根长度互不相同且能组成三角形的木棍？ 也就是说，求满足下列两个条件的整数三元组 $(i, j, k)$ (1 \leq i < j < k \leq N) 的个数：

$L_i$、$L_j$ 和 $L_k$ 两两不同。 存在一条边长分别为 $L_i$、$L_j$、$L_k$ 的三角形。

输入格式

输入按下述格式由标准输入给出： $N$ $L_1$ $L_2$ $\cdots$ $L_N$

输出格式

输出可以选择的三根长度互不相同且能组成三角形的木棍的方案数。

5
4 4 9 7 5

5

6
4 5 4 3 3 5

8

10
9 4 6 1 9 6 10 6 6 8

39

2
1 1

0

提示

$1 \leq N \leq 100$ $1 \leq L_i \leq 10^9$ 输入中的所有数值均为整数。下列五个三元组 $(i, j, k)$ 满足条件：$(1, 3, 4)$、$(1, 4, 5)$、$(2, 3, 4)$、$(2, 4, 5)$、和 $(3, 4, 5)$。
我们对于长度 $3$、$4$、$5$ 各有两根木棍。为了满足第一个条件，我们必须从每个长度中各选一根。 存在一条边长为 $3$、$4$、$5$ 的三角形，因此有 $2 ^ 3 = 8$ 个满足条件的三元组 $(i, j, k)$。
没有满足 1 \leq i < j < k \leq N 的三元组 $(i, j, k)$，所以应当输出 $0$。

标签: AtCoder|abc175B

来源

AtCoder|abc175B