题目描述

给你一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$。
你可以对数组执行以下两种操作任意次：

• 从数组中选择两个值相等的元素，并将它们从数组中删除。
• 从数组中选择三个值相等的元素，并将它们从数组中删除。

请你输出使数组为空的最少操作次数，如果无法达成，请输出 $-1$。

输入格式

第一行一个整数 $n$。
第二行 $n$ 个整数 $a_1,a_2,...,a_n$。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

9
2 3 3 2 2 4 2 3 4

输出 #1

4

输入输出样例 #2

输入 #2

6
2 1 2 2 3 3

输出 #2

-1

说明/提示

$2\le n\le 5\times 10^5,1\le a_i\le 10^6$。