题目描述

小$\tt Z$ 正在玩一个数字游戏。他有一个包含 $N$ 个非负整数的数组，其中有些位置可能是 $0$。游戏规则如下：

• 找到数组中所有值为 $0$ 的位置；
• 将这些 $0$ 替换成任意你想要的数字；
• 目标是通过替换，使数组中相等的数字对尽可能多；

相等数字对：满足 $i < j$ 且 $A_i = A_j$ 的不同索引对 $(i,j)$ 的数量。

输入格式

第一行是 $N$，表示数组大小。

第二行是 $N$ 个空格分隔的整数 $A₁, A₂, …, A_n$。

输出格式

输出一个整数，表示通过最优替换后数组中可能的最大相等数字对数。

输入输出样例

5
1 3 1 4 4

2

样例 $\tt \#1$说明

• 数组中有两对相等的元素：分别为$(1,1)$ 和 $(4,4)$。

5
3 3 2 0 0

6

样例 $\tt \#2$说明

• 将两个 $0$ 替换为 $3$ 后，数组变为 $[3,3,2,3,3]$，共有 $6$ 对相等的元素，下标为 $(1,2),(1,4),(1,5),(2,4),(2,5),(4,5)$。

3
0 0 0

3

数据范围

• 对于 $30\%$ 的数据，$1\le a_i\le 100, 1\le n \le 100$，即不存在零元素替换。
• 对于另外 $40\%$ 的数据，$1\le n \le 1000$。
• 对于 $100\%$ 的数据，$1 \le n \le 10^5, 0 \le a_i \le 100$。