{"raw_statement":[{"iden":"statement","content":"Hideo Kojima has just quit his job at Konami. Now he is going to find a new place to work. Despite being such a well-known person, he still needs a CV to apply for a job.\n\nDuring all his career Hideo has produced _n_ games. Some of them were successful, some were not. Hideo wants to remove several of them (possibly zero) from his CV to make a better impression on employers. As a result there should be no unsuccessful game which comes right after successful one in his CV.\n\nMore formally, you are given an array _s_1, _s_2, ..., _s__n_ of zeros and ones. Zero corresponds to an unsuccessful game, one — to a successful one. Games are given in order they were produced, and Hideo can't swap these values. He should remove some elements from this array in such a way that no zero comes right after one.\n\nBesides that, Hideo still wants to mention as much games in his CV as possible. Help this genius of a man determine the maximum number of games he can leave in his CV."},{"iden":"input","content":"The first line contains one integer number _n_ (1 ≤ _n_ ≤ 100).\n\nThe second line contains _n_ space-separated integer numbers _s_1, _s_2, ..., _s__n_ (0 ≤ _s__i_ ≤ 1). 0 corresponds to an unsuccessful game, 1 — to a successful one."},{"iden":"output","content":"Print one integer — the maximum number of games Hideo can leave in his CV so that no unsuccessful game comes after a successful one."},{"iden":"examples","content":"Input\n\n4\n1 1 0 1\n\nOutput\n\n3\n\nInput\n\n6\n0 1 0 0 1 0\n\nOutput\n\n4\n\nInput\n\n1\n0\n\nOutput\n\n1"}],"translated_statement":[{"iden":"statement","content":"Hideo Kojima 刚刚从 Konami 辞职。现在他需要找一份新工作。尽管他是一位广为人知的人物，但他仍然需要一份简历来申请职位。\n\n在他整个职业生涯中，Hideo 制作了 #cf_span[n] 款游戏。其中一些是成功的，一些是失败的。Hideo 希望从他的简历中删除若干款游戏（可能为零款），以给雇主留下更好的印象。结果，他的简历中不应出现任何失败的游戏紧接在成功游戏之后的情况。\n\n更正式地，你被给定一个由 0 和 1 组成的数组 #cf_span[s1, s2, ..., sn]。0 对应一个失败的游戏，1 对应一个成功的游戏。游戏按其被制作的顺序给出，Hideo 不能交换这些值。他应从该数组中删除某些元素，使得没有任何 0 紧接在 1 之后。\n\n此外，Hideo 仍希望在他的简历中尽可能多地保留游戏。请帮助这位天才确定他最多可以保留多少款游戏。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[s1, s2, ..., sn]（#cf_span[0 ≤ si ≤ 1]）。#cf_span[0] 对应一个失败的游戏，#cf_span[1] 对应一个成功的游戏。\n\n请输出一个整数——Hideo 可以保留在简历中的最大游戏数量，使得没有任何失败的游戏出现在成功游戏之后。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[s1, s2, ..., sn]（#cf_span[0 ≤ si ≤ 1]）。#cf_span[0] 对应一个失败的游戏，#cf_span[1] 对应一个成功的游戏。"},{"iden":"output","content":"请输出一个整数——Hideo 可以保留在简历中的最大游戏数量，使得没有任何失败的游戏出现在成功游戏之后。"},{"iden":"examples","content":"输入\n4\n1 1 0 1\n输出\n3\n\n输入\n6\n0 1 0 0 1 0\n输出\n4\n\n输入\n1\n0\n输出\n1"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ s = [s_1, s_2, \\dots, s_n] $ be a binary sequence where $ s_i \\in \\{0, 1\\} $.\n\n**Constraint:**  \nThe resulting subsequence must not contain any occurrence of $ 1 $ immediately followed by $ 0 $, i.e., no substring \"10\".\n\n**Objective:**  \nMaximize the length of a subsequence (not necessarily contiguous, but preserving order) of $ s $ satisfying the above constraint.\n\n---\n\n**Formal Problem Statement:**\n\nGiven a binary sequence $ s \\in \\{0,1\\}^n $, find the maximum length of a subsequence $ s' $ of $ s $ such that there do not exist indices $ i < j $ in $ s' $ with $ s'_i = 1 $ and $ s'_j = 0 $.\n\n---\n\n**Equivalent Reformulation:**\n\nThe constraint \"no 1 followed by 0\" implies that in the resulting subsequence, all 0s must come before all 1s. That is, the subsequence must be of the form:\n\n$$\n\\underbrace{0, 0, \\dots, 0}_{a \\text{ times}}, \\underbrace{1, 1, \\dots, 1}_{b \\text{ times}}\n$$\n\nfor some $ a, b \\geq 0 $.\n\nThus, the problem reduces to:  \nFind the maximum value of $ a + b $, where $ a $ is the number of 0s selected from some prefix of $ s $, and $ b $ is the number of 1s selected from the corresponding suffix of $ s $, such that all selected 0s appear before all selected 1s in the original sequence.\n\n---\n\n**Optimization Strategy:**\n\nFor each possible split point $ k \\in \\{0, 1, \\dots, n\\} $, consider:\n- Taking all 0s from positions $ 1 $ to $ k $,\n- Taking all 1s from positions $ k+1 $ to $ n $.\n\nThen the total length is:\n$$\n\\text{count}_0(1..k) + \\text{count}_1(k+1..n)\n$$\n\nThe maximum over all $ k \\in \\{0, 1, \\dots, n\\} $ gives the answer.\n\n---\n\n**Final Mathematical Formulation:**\n\nLet $ n \\in \\mathbb{N} $, $ s \\in \\{0,1\\}^n $.  \nDefine for $ k \\in \\{0, 1, \\dots, n\\} $:\n\n$$\nf(k) = \\sum_{i=1}^{k} [s_i = 0] + \\sum_{i=k+1}^{n} [s_i = 1]\n$$\n\nThen the answer is:\n\n$$\n\\max_{k \\in \\{0, 1, \\dots, n\\}} f(k)\n$$","simple_statement":null,"has_page_source":false}