{"raw_statement":[{"iden":"statement","content":"There were _n_ groups of students which came to write a training contest. A group is either one person who can write the contest with anyone else, or two people who want to write the contest in the same team.\n\nThe coach decided to form teams of exactly three people for this training. Determine the maximum number of teams of three people he can form. It is possible that he can't use all groups to form teams. For groups of two, either both students should write the contest, or both should not. If two students from a group of two will write the contest, they should be in the same team."},{"iden":"input","content":"The first line contains single integer _n_ (2 ≤ _n_ ≤ 2·105) — the number of groups.\n\nThe second line contains a sequence of integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 2), where _a__i_ is the number of people in group _i_."},{"iden":"output","content":"Print the maximum number of teams of three people the coach can form."},{"iden":"examples","content":"Input\n\n4\n1 1 2 1\n\nOutput\n\n1\n\nInput\n\n2\n2 2\n\nOutput\n\n0\n\nInput\n\n7\n2 2 2 1 1 1 1\n\nOutput\n\n3\n\nInput\n\n3\n1 1 1\n\nOutput\n\n1"},{"iden":"note","content":"In the first example the coach can form one team. For example, he can take students from the first, second and fourth groups.\n\nIn the second example he can't make a single team.\n\nIn the third example the coach can form three teams. For example, he can do this in the following way:\n\n*   The first group (of two people) and the seventh group (of one person),\n*   The second group (of two people) and the sixth group (of one person),\n*   The third group (of two people) and the fourth group (of one person)."}],"translated_statement":[{"iden":"statement","content":"有 #cf_span[n] 组学生前来参加训练赛。每组要么是单个学生，可以与任何人组队；要么是两人组，希望在同一队中参赛。\n\n教练决定为此次训练赛组建恰好三人一队的队伍。请确定他最多能组成多少支三人队伍。可能无法使用所有组来组建队伍。对于两人组，要么两名学生都参赛，要么都不参赛；如果两人组中的两名学生参赛，他们必须在同一队中。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2·105]) —— 组的数量。\n\n第二行包含一个整数序列 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 2])，其中 #cf_span[ai] 表示第 #cf_span[i] 组的人数。\n\n请输出教练能组成的三人队伍的最大数量。\n\n在第一个示例中，教练可以组成一支队伍。例如，他可以从第一、第二和第四组中选取学生。\n\n在第二个示例中，他无法组成任何一支队伍。\n\n在第三个示例中，教练可以组成三支队伍。例如，他可以按以下方式操作：\n\n"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2·105]) —— 组的数量。第二行包含一个整数序列 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 2])，其中 #cf_span[ai] 表示第 #cf_span[i] 组的人数。"},{"iden":"output","content":"请输出教练能组成的三人队伍的最大数量。"},{"iden":"examples","content":"输入41 1 2 1输出1输入22 2输出0输入72 2 2 1 1 1 1输出3输入31 1 1输出1"},{"iden":"note","content":"在第一个示例中，教练可以组成一支队伍。例如，他可以从第一、第二和第四组中选取学生。在第二个示例中，他无法组成任何一支队伍。在第三个示例中，教练可以组成三支队伍。例如，他可以按以下方式操作：第一组（两人）与第七组（一人），第二组（两人）与第六组（一人），第三组（两人）与第四组（一人）。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of groups.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence where $ a_i \\in \\{1, 2\\} $ denotes the size of group $ i $.  \n\nLet:  \n- $ c_1 = |\\{i \\mid a_i = 1\\}| $: number of singleton groups.  \n- $ c_2 = |\\{i \\mid a_i = 2\\}| $: number of two-person groups.  \n\n**Constraints**  \n$ 2 \\leq n \\leq 2 \\cdot 10^5 $,  \n$ c_1 + c_2 = n $,  \n$ c_1, c_2 \\in \\mathbb{Z}_{\\geq 0} $.  \n\n**Objective**  \nMaximize the number of teams of exactly three people, subject to:  \n- Each team consists of exactly three students.  \n- Each two-person group must be kept intact (both students in the same team) or not used at all.  \n- Singleton groups can be freely assigned to any team.  \n\nLet $ t $ be the number of teams formed.  \nLet $ x \\in \\{0, 1, \\dots, c_2\\} $ be the number of two-person groups used (each contributing 2 students).  \nThen the remaining $ 3t - 2x $ students must come from singleton groups, so:  \n$ 3t - 2x \\leq c_1 $ and $ 3t - 2x \\geq 0 $.  \n\nThus, for fixed $ x $, the maximum number of teams is:  \n$$\nt = \\left\\lfloor \\frac{c_1 + 2x}{3} \\right\\rfloor\n$$  \nwith constraint $ 0 \\leq x \\leq c_2 $ and $ 2x \\leq 3t \\leq c_1 + 2x $.  \n\n**Objective:**  \n$$\n\\max_{x \\in \\{0, 1, \\dots, c_2\\}} \\left\\lfloor \\frac{c_1 + 2x}{3} \\right\\rfloor\n$$","simple_statement":null,"has_page_source":false}