三元组(Triple)

题目描述

给定 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，小爱每次可以选出一个满足 $i\neq j\neq k$ 且 $a_i\neq a_j\neq a_k$ 的三元组 $(a_i,a_j,a_k)$，并将这三个数字删去，直到剩余的数字无法再组成满足条件的三元组为止。请问在最优决策情况下，最终最少会剩下多少个数字无法组成三元组。

输入格式

输入共两行：

• 第一行：一个正整数 $n$
• 第二行：$n$ 个整数 $a_1,a_2,\ldots,a_n$

输出格式

输出共一行：一个整数，表示最优情况下最少剩下的数字的个数。

样例输入 #1

6
1 1 1 1 2 3

样例输出 #1

3

说明：将 $(1,2,3)$ 三元组删去后，剩下 $3$ 个 $1$ 无法继续组成三元组

样例输入 #2

6
1 2 3 3 4 5

样例输出 #2

0

说明：原序列可以组成 $(1,2,3),(3,4,5)$ 两个三元组，剩余数字个数为 $0$ 个

数据范围

• 对于 $30\%$ 的数据，$1\leq n \leq 100$
• 对于 $70\%$ 的数据，$1\leq n \leq 10^4$，$1\leq a_i\leq 10^5$
• 对于 $100\%$ 的数据，$1\leq n \leq 10^5$，$-10^9\leq a_i\leq 10^9$

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐。

测试点分布