题目描述
小 C 有一个长度为 n 的序列 A。
小 C 认为一个三元组 (i,j,k)(i=j,i=k,j=k) 是好的,当且仅当存在正整数 b 满足 AiAj=AjAk=b。
小 C 想要知道对于序列 A 而言有多少个好的三元组?
输入格式
输入的第一行包含一个整数 n。
接下来一行包含 n 个整数,第 i 个整数表示 Ai。
输出格式
输出共一行,包含一个整数,表示好的三元组个数。
样例 1 输入
3
6 2 18
样例 1 输出
1
样例 1 解释
只有三元组 (2,1,3) 是好的。
样例 2 输入
5
1 2 7 7 7
样例 2 输出
6
其余样例见下发文件。
数据规模与约定
- 对于 20% 的数据,保证 n≤500。
- 对于 40% 的数据,保证 n≤5000。
- 对于另 20% 的数据,保证 maxAi≤5000。
- 对于另 20% 的数据,保证 maxAi≤106。
- 对于 100% 的数据,保证 1≤n≤105,1≤Ai≤109。