题目描述

给定$n$个正整数$a_1,a_2,...,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,...,a_n$

输出格式

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

6
1 1 1 1 2 3

3

样例解释 1

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

6
1 2 3 3 4 5

0

样例解释 2

原序列可以组成(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$