题目描述

小 C 有一个长度为 $n$ 的序列 $A$。

小 C 认为一个三元组 $(i,j,k)(i\ne j,i\ne k,j\ne k)$ 是好的，当且仅当存在正整数 $b$ 满足 $\frac{A_j}{A_i}=\frac{A_k}{A_j}=b$。

小 C 想要知道对于序列 $A$ 而言有多少个好的三元组？

输入格式

输入的第一行包含一个整数 $n$。

接下来一行包含 $n$ 个整数，第 $i$ 个整数表示 $A_i$。

输出格式

输出共一行，包含一个整数，表示好的三元组个数。

3
6 2 18

1

5
1 2 7 7 7

6

数据范围

样例 1 解释

只有三元组 $(2,1,3)$ 是好的。

• 对于 $20\%$ 的数据，保证 $n \le 500$。
• 对于 $40\%$ 的数据，保证 $n \le 5000$。
• 对于另 $20\%$ 的数据，保证 $\max A_i \le 5000$。
• 对于另 $20\%$ 的数据，保证 $\max A_i \le 10^6$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$1\le A_i\le 10^{9}$。