题目描述

给你 $n$ 个数字，分别为 $a_1,a_2,\dots a_n$，你每次操作可以从其中选择两个或者三个相等的数字，然后将其删除。

请问你至少操作多少次，才能将所有的数字全部消除？如果无法将数字全部消除，请输出-1。

输入格式

第一行包含一个整数 $n$，表示数字的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每个数字的值。

输出格式

一行一个整数，表示将所有数字消除所需要的最少操作次数，如果无法全部消除，输出-1。

样例

输入样例1

5
2 2 2 3 3

输出样例1

2

解释：第一次消除前面 $3$ 个 $2$，第二次消除后面 $2$ 个 $3$。

输入样例2

5
2 2 2 3 4

输出样例2

-1

解释：$3$ 和 $4$ 都只有 $1$ 个，无法消除。

数据范围与提示

对于 $30\%$ 的数据，$1 \le n \le 100$ ， $1 \le a_i \le 2$。

另有 $30\%$ 的数据，$任意, i,j 属于 [1, n]，都有 a_i = a_j$ ，即所有数字均相等。

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