English · Original
Chinese · Translation
Formal · Original
_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._
A 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_.
Little 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.
A 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_.
## Input
The first line contains an integer _n_ (1 ≤ _n_ ≤ 2000), denoting the length of the original sequence.
The 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_).
## Output
Print a single integer, which means the maximum possible length of the longest non-decreasing subsequence of the new sequence.
[samples]
## Note
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.
In 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.
_龙象征着智慧、力量与财富。在农历新年当天，人们用竹条和布料制作龙的模型，用杆子抬起它们，并高低挥动杆子以模拟飞龙的姿态。_
持杆较低的表演者用 #cf_span[1] 表示，持杆较高的表演者用 #cf_span[2] 表示。因此，表演者的队列可以用序列 #cf_span[a1, a2, ..., an] 表示。
小汤米是其中一员。他希望选择一个区间 #cf_span[[l, r]] (#cf_span[1 ≤ l ≤ r ≤ n])，然后将 #cf_span[al, al + 1, ..., ar] 反转，使得新序列的最长非递减子序列的长度最大化。
非递减子序列是指一组下标 #cf_span[p1, p2, ..., pk]，满足 #cf_span[p1 < p2 < ... < pk] 且 #cf_span[ap1 ≤ ap2 ≤ ... ≤ apk]。该子序列的长度为 #cf_span[k]。
第一行包含一个整数 #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)]。
请输出一个整数，表示新序列的最长非递减子序列可能的最大长度。
在第一个例子中，反转 #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]。
## Input
第一行包含一个整数 #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)]。
## Output
请输出一个整数，表示新序列的最长非递减子序列可能的最大长度。
[samples]
## Note
在第一个例子中，反转 #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]。
**Definitions**
Let $ n \in \mathbb{Z} $ be the length of the sequence.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence where $ a_i \in \{1, 2\} $ for all $ i \in \{1, \dots, n\} $.
For any interval $ [l, r] $ with $ 1 \leq l \leq r \leq n $, define the transformed sequence $ A^{(l,r)} $ as:
$$
A^{(l,r)}_i =
\begin{cases}
a_{l + r - i} & \text{if } l \leq i \leq r, \\
a_i & \text{otherwise}.
\end{cases}
$$
Let $ \text{LNS}(B) $ denote the length of the longest non-decreasing subsequence of a sequence $ B $.
**Constraints**
$ 1 \leq n \leq 2000 $, and $ a_i \in \{1, 2\} $ for all $ i $.
**Objective**
Compute:
$$
\max_{1 \leq l \leq r \leq n} \text{LNS}\left(A^{(l,r)}\right)
$$
API Response (JSON)
{
"problem": {
"name": "C. 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": "CF934C"
},
"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 ...",
"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...",
"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 where $ a_i \\in \\{1, 2\\} $ for all $ i \\in \\{1, \\dots, n\\} $. \n\nFor any in...",
"is_translate": false,
"language": "Formal"
}
]
}