思路：优先队列

统计每个数的个数，然后用一个优先队列维护每个数，按照每个数出现的次数的一个小根堆。

一个贪心想法是，考虑每个数先和其他每个数配对一次，然后剩余多的数再自己和自己匹配。

因为总共有 $n$ 个数，每个数至多各进出一次优先队列。

至于为什么需要先和其他数匹配，再和自己匹配。

题目内容

炼金术士收集了 $n$ 份原始材料，每份材料都有一个魔力值。当他将两份材料进行融合时，会触发一种共鸣效果。共鸣效果的类型完全由这两份材料的魔力值决定，且与材料的顺序无关（即魔力值 $x$ 与 $y$ 的融合和 $y$ 与 $x$ 的融合视为同一种效果）。术士想要尽可能多地发现不同种类的共鸣效果。同一种效果即使被触发多次，也只算作一种。现在给定所有材料的魔力值，请你帮他计算最多能发现多少种不同的共鸣效果。

材料数量 $n$ 满足 $1 \le n \le 10^5$，每份材料的魔力值 $a_i$ 满足 $1 \le a_i \le 10^9$。

输入描述

第一行包含一个整数 $n$，表示材料的数量。 第二行包含 $n$ 个整数，依次表示每份材料的魔力值。

输出描述

输出一个整数，表示最多能发现的不同共鸣效果的种类数。

样例1

输入

2
5 7

输出

1

说明

有 2 份材料，魔力值分别为 5 和 7。只能进行一次融合，产生的共鸣效果类型为 $(5,7)$，因此最多发现 1 种不同效果。

样例2

输入

4
1 2 3 4

输出

2

说明

四份材料魔力值各不相同，分别为 1、2、3、4。可以将材料两两配对融合，例如 $(1,2)$ 和 $(3,4)$，这样能发现 2 种不同的共鸣效果。由于每份材料只能使用一次，无法得到更多的不同效果，故答案为 2。

样例3

输入

6
10 10 20 20 30 30

输出

3

说明

三种魔力值 10、20、30 各出现 $2$ 次。可以做如下融合：第一次将 10 与 20 融合得到效果 $(10,20)$；第二次将 10 与 30 融合得到效果 $(10,30)$；第三次将 20 与 30 融合得到效果 $(20,30)$。所有材料刚好用完，共发现 3 种不同的共鸣效果。

样例4

输入

5
1 1 1 2 3

输出

2

说明

魔力值 1 有 $3$ 份，2 和 3 各 $1$ 份。 首先用一份 1 与 2 融合，得到效果 $(1,2)$； 再用一份 1 与 3 融合，得到效果 $(1,3)$； 此时 1 还剩 $1$ 份，但 2 和 3 已被消耗，无法再与不同魔力值融合产生新效果。 由于同种效果只算一次，且无法自我配对（1 仅剩一份），因此最终能发现的不同共鸣效果种类数为 2。