Description

世界编程竞赛的参与者向评分系统提交了 $N$ 个解决方案文件 $f_1 ,...,f_N$。在接受结果为最终结果之前，评审团希望排除任何抄袭的可能性。他们有一个程序，可以将两个文件进行比较，以决定它们是否过于相似。然而，文件的数量相当大，比较所有对将花费太多时间。另一方面，许多对可以基于文件大小差异过大而快速排除。更确切地说，评审团决定完全跳过比较每一对，其中较小文件的大小小于较大文件大小的 90%。因此，比较程序只需检查那些不同的文件对 $(f_i, f_j)$，其中 $i \ne j, size(f_i) \le size(f_j)$ 且 $size(f_i) \ge 0.9 \times size(f_j)$。编写一个程序来计算需要检查的文件对的数量。

Input Format

输入的第一行包含整数 $N$，表示提交的解决方案文件的数量。第二行包含 $N$ 个整数 $size(f_1),\cdots,size(f_N)$，每个整数表示一个文件的大小。

Output Format

输出的第一行且唯一一行必须包含一个整数，即需要检查的文件对的数量。

2
2 1

0

5
1 1 1 1 1

10

Hint

对于 $50\%$ 的数据，$1 \le N \le 2000$。对于所有数据，$1 \le N \le 10^5,1 \le f_i \le 10^8$。

题面翻译由 ChatGPT-4o 提供。