← 返回题目列表

Codeforces · 899/A

A. 分组

中文机器翻译题面 查看原题

有n组学生来参加写作训练比赛。一个小组可以是一个可以与其他人一起撰写竞赛的人,也可以是两个想要在同一团队中撰写竞赛的人。

教练决定本次训练正好三人一组。确定他可以组建的三人团队的最大数量。他有可能无法利用所有的团体来组队。对于两人一组,要么两个学生都应该写比赛,要么两个人都不应该写比赛。如果两人一组中的两名学生参加比赛,他们应该在同一个团队中。

输入

第一行包含单个整数 n (2 ≤ n ≤ 2·105) — 组数。

第二行包含整数序列 a1, a2, ..., an (1 ≤ ai ≤ 2),其中 ai 是第 i 组中的人数。

输出

打印教练可以组建的最大三人团队数量。

示例

输入 #1

4
1 1 2 1

输出 #1

1

输入 #2

2
2 2

输出 #2

0

输入 #3

7
2 2 2 1 1 1 1

输出 #3

3

输入#4

3
1 1 1

输出#4

1

注意

在第一个示例中,教练可以组建一个团队。比如他可以带第一组、第二组、第四组的学生。

在第二个示例中,他无法组成一个团队。

在第三个示例中,教练可以组建三个团队。例如,他可以通过以下方式做到这一点:

- 第一组(两人)和第七组(一人),
- 第二组(两人)和第六组(一人),
- 第三组(两人)和第四组(一人)。