题目描述

有 $n$ 个学生小组前来参加训练赛。小组分为两种：一种是只有一个人的小组，他可以和任何人组队；另一种是有两个人的小组，他们想一起参加比赛，必须在同一个队伍中。

教练决定组成每队恰好三人的训练队。请你计算他最多可以组成多少支三人小队。注意，可能无法用完所有小组来组成队伍。对于两人小组，要么两人全都参加，要么两人都不参加，并且如果选中了该小组，两人必须在同一队。

输入格式

第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$），表示小组数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 2$），其中 $a_i$ 表示第 $i$ 个小组的人数。

输出格式

输出教练能组成的三人小队的最大数量。

说明/提示

在第一个样例中，教练可以组成一支队伍。例如，可以从第 1、2、4 个小组各选一人组队。

在第二个样例中，无法组成任何队伍。

在第 3 个样例中，教练可以组成 3 支队伍。例如，可以按如下方式分组：

• 第一个两人小组和第七个一人小组，
• 第二个两人小组和第六个一人小组，
• 第三个两人小组和第四个一人小组。

由 ChatGPT 5 翻译

样例

4
1 1 2 1

1

2
2 2

0

7
2 2 2 1 1 1 1

3

3
1 1 1

1