题目描述

有 $n$ 顶帽子，第 $i$ 顶帽子的颜色是 $a_i$。

33DAI 和 Kitten 每次出门都会选择两顶颜色相同的、没穿过的帽子。请问他们能出门多少次。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数，即 $a_1\sim a_n$。

输出格式

一行一个整数，表示他们能出门多少次。

10
3 3 1 3 1 3 4 3 1 1

4

样例解释

() 表示之前选过的帽子，{} 表示当天选择的帽子。

• 第一天可以选择两顶颜色为 3 的帽子：
  • {3} {3} 1 3 1 3 4 3 1 1
• 第二天可以选择两顶颜色为 1 的帽子：
  • (3) (3) {1} 3 {1} 3 4 3 1 1
• 第三天可以选择两顶颜色为 3 的帽子：
  • (3) (3) (1) {3} (1) {3} 4 3 1 1
• 第四天可以选择两顶颜色为 1 的帽子：
  • (3) (3) (1) (3) (1) (3) 4 3 {1} {1}

数据规模与约定

对于 $100\%$ 的数据，$1\le n \le 10^5$，$1\le a_i\le 10^9$

• 子任务 1（30 分）：$1\le n\le 1000$
• 子任务 2（30 分）：$1\le a_i\le 1000$
• 子任务 3（40 分）：无特殊限制