You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在某一个平行世界中，每个人的姓名有三个字，且三个字的读音都必须不相同，否则姓名不合法。例如 ji-wei-jiu 是一个合法的名字；而 yao-wang 则不是，因为只有两个字；li-yi-yi 也不是，因为有两个读音相同的字。

如果有三个人的名字具有题目中的特性，则我们称这三个人为一个“姓名团”。特性如下：你可以选出三个不同的字，使得每个字都被这三个人中的至少两人的名字包含。

例如第一个人叫 wu-si-cheng，第二个人叫 wu-jia-han，第三个人叫 chen-si-han。那么当你选择 wu 的时候，前两个人包含这个字，选择 si 的时候，第一和第三个人包含这个字，选择 han 的时候，第二和第三个人包含这个字。（只需要包含这个字即可，无需关心这个字在名字中的位置）

即对于 wu-si-han 这三个字，每一个字都被至少两人包含。

注意： 每个人只能处于一个姓名团中，在任意范围内，不同人之间的名字可以相同。

现在你有一个包含 $n$ 个字的字库，每个字可以用 $a_i$ 次，我们假设所有字的使用次数之和为 $sum$(保证 sum 是 3 的倍数)，那么你就可以造出 $sum/3$ 个人名出来。请问你最多能造出多少个姓名团。

如果不能造出 $sum/3$ 个合法人名，输出 -1。

输入格式

第一行输入一个整数 $n$，表示字库中共有 $n$ 个字。接下来一行包含 $n$ 个正整数 $a_i$，分别表示每个字能够使用的次数，保证所有 $a_i$ 之和是 3 的倍数。

输出格式

输出一行一个整数表示结果。

3
10 1 1

-1

3
4 4 4

1

大样例

T4.in
T4.out

样例 2 说明：总共可以造出 4 个名字一样的人，但是由于一个姓名团需要包含 3 个人，所以只能有一个姓名团。

测试点信息