有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
注意
在第一个示例中,教练可以组建一个团队。比如他可以带第一组、第二组、第四组的学生。
在第二个示例中,他无法组成一个团队。
在第三个示例中,教练可以组建三个团队。例如,他可以通过以下方式做到这一点:
- 第一组(两人)和第七组(一人),
- 第二组(两人)和第六组(一人),
- 第三组(两人)和第四组(一人)。