{"problem":{"name":"A. A Twisty Movement","description":{"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF933A"},"statements":[{"statement_type":"Markdown","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_.\n\n## Input\n\nThe 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_).\n\n## Output\n\nPrint a single integer, which means the maximum possible length of the longest non-decreasing subsequence of the new sequence.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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## Input\n\n第一行包含一个整数 #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)]。\n\n## Output\n\n请输出一个整数，表示新序列的最长非递减子序列可能的最大长度。\n\n[samples]\n\n## Note\n\n在第一个示例中，反转 #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]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the sequence.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence with $ 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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF933A","tags":["dp"],"sample_group":[["4\n1 2 1 2","4"],["10\n1 1 2 2 2 1 1 2 2 1","9"]],"created_at":"2026-03-03 11:00:39"}}