{"raw_statement":[{"iden":"statement","content":"_A dragon symbolizes wisdom, power and wealth. On Lunar New Year's Day, people model a dragon with bamboo strips and clothes, raise them with rods, and hold the rods high and low to resemble a flying dragon._\n\nA performer holding the rod low is represented by a 1, while one holding it high is represented by a 2. Thus, the line of performers can be represented by a sequence _a_1, _a_2, ..., _a__n_.\n\nLittle Tommy is among them. He would like to choose an interval \\[_l_, _r_\\] (1 ≤ _l_ ≤ _r_ ≤ _n_), then reverse _a__l_, _a__l_ + 1, ..., _a__r_ so that the length of the longest non-decreasing subsequence of the new sequence is maximum.\n\nA non-decreasing subsequence is a sequence of indices _p_1, _p_2, ..., _p__k_, such that _p_1 < _p_2 < ... < _p__k_ and _a__p_1 ≤ _a__p_2 ≤ ... ≤ _a__p__k_. The length of the subsequence is _k_."},{"iden":"input","content":"The first line contains an integer _n_ (1 ≤ _n_ ≤ 2000), denoting the length of the original sequence.\n\nThe second line contains _n_ space-separated integers, describing the original sequence _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 2, _i_ = 1, 2, ..., _n_)."},{"iden":"output","content":"Print a single integer, which means the maximum possible length of the longest non-decreasing subsequence of the new sequence."},{"iden":"examples","content":"Input\n\n4\n1 2 1 2\n\nOutput\n\n4\n\nInput\n\n10\n1 1 2 2 2 1 1 2 2 1\n\nOutput\n\n9"},{"iden":"note","content":"In the first example, after reversing \\[2, 3\\], the array will become \\[1, 1, 2, 2\\], where the length of the longest non-decreasing subsequence is 4.\n\nIn the second example, after reversing \\[3, 7\\], the array will become \\[1, 1, 1, 1, 2, 2, 2, 2, 2, 1\\], where the length of the longest non-decreasing subsequence is 9."}],"translated_statement":[{"iden":"statement","content":"_龙象征着智慧、力量与财富。在农历新年当天，人们用竹条和布料制作龙的模型，用杆子抬起它们，并高低挥动杆子以模拟飞龙的姿态。_\n\n持杆较低的表演者用 #cf_span[1] 表示，持杆较高的表演者用 #cf_span[2] 表示。因此，表演者的队列可以用序列 #cf_span[a1, a2, ..., an] 表示。\n\n小汤米是其中一员。他希望选择一个区间 #cf_span[[l, r]] (#cf_span[1 ≤ l ≤ r ≤ n])，然后将 #cf_span[al, al + 1, ..., ar] 反转，使得新序列的最长非递减子序列的长度最大化。\n\n非递减子序列是指一组下标 #cf_span[p1, p2, ..., pk]，满足 #cf_span[p1 < p2 < ... < pk] 且 #cf_span[ap1 ≤ ap2 ≤ ... ≤ apk]。该子序列的长度为 #cf_span[k]。\n\n第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 2000)]，表示原序列的长度。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数，描述原序列 #cf_span[a1, a2, ..., an] #cf_span[(1 ≤ ai ≤ 2, i = 1, 2, ..., n)]。\n\n请输出一个整数，表示新序列的最长非递减子序列可能的最大长度。\n\n在第一个例子中，反转 #cf_span[[2, 3]] 后，数组变为 #cf_span[[1, 1, 2, 2]]，其中最长非递减子序列的长度为 #cf_span[4]。\n\n在第二个例子中，反转 #cf_span[[3, 7]] 后，数组变为 #cf_span[[1, 1, 1, 1, 2, 2, 2, 2, 2, 1]]，其中最长非递减子序列的长度为 #cf_span[9]。\n\n"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 2000)]，表示原序列的长度。第二行包含 #cf_span[n] 个用空格分隔的整数，描述原序列 #cf_span[a1, a2, ..., an] #cf_span[(1 ≤ ai ≤ 2, i = 1, 2, ..., n)]。"},{"iden":"output","content":"请输出一个整数，表示新序列的最长非递减子序列可能的最大长度。"},{"iden":"examples","content":"输入41 2 1 2输出4输入101 1 2 2 2 1 1 2 2 1输出9"},{"iden":"note","content":"在第一个例子中，反转 #cf_span[[2, 3]] 后，数组变为 #cf_span[[1, 1, 2, 2]]，其中最长非递减子序列的长度为 #cf_span[4]。在第二个例子中，反转 #cf_span[[3, 7]] 后，数组变为 #cf_span[[1, 1, 1, 1, 2, 2, 2, 2, 2, 1]]，其中最长非递减子序列的长度为 #cf_span[9]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the sequence.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence where $ a_i \\in \\{1, 2\\} $ for all $ i \\in \\{1, \\dots, n\\} $.  \n\nFor any interval $ [l, r] $ with $ 1 \\leq l \\leq r \\leq n $, define the transformed sequence $ A^{(l,r)} $ as:  \n$$\nA^{(l,r)}_i = \n\\begin{cases}\na_{l + r - i} & \\text{if } l \\leq i \\leq r, \\\\\na_i & \\text{otherwise}.\n\\end{cases}\n$$\n\nLet $ \\text{LNS}(B) $ denote the length of the longest non-decreasing subsequence of a sequence $ B $.\n\n**Constraints**  \n$ 1 \\leq n \\leq 2000 $, and $ a_i \\in \\{1, 2\\} $ for all $ i $.\n\n**Objective**  \nCompute:\n$$\n\\max_{1 \\leq l \\leq r \\leq n} \\text{LNS}\\left(A^{(l,r)}\\right)\n$$","simple_statement":null,"has_page_source":false}