Codeforces Round #462 (Div. 2) C. A Twisty Movement （前缀和）

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 a1, a2, ..., an.

Little Tommy is among them. He would like to choose an interval [l, r] (1 ≤ l ≤ r ≤ n), then reverse al, al + 1, ..., ar 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 p1, p2, ..., pk, such that p1 < p2 < ... < pk and ap1 ≤ ap2 ≤ ... ≤ apk. 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 a1, a2, ..., an (1 ≤ ai ≤ 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.

Examples

input

Copy

4
1 2 1 2

output

input

Copy

10
1 1 2 2 2 1 1 2 2 1

output

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.

题意就是在给出来的字符串里，找到一个最长非递增子串把它倒序，使得整个字符串存在一个最长的非递减子串。并输出长度。

这个题一开始看起来非常棘手，因为暴力很难切入，但是因为字符串里只有1和2，而且这个子串一定是222222222222221111111111111形式的，那么我们只要找到这个子串分界的地方就好了，我把最后一个2（就是1前面那个2）标记成k，然后枚举这个子串的首尾（l,r）因为1在前，2在后，我们需要维护一个1的前缀和pre1[]和2的后缀和aft2[]，然后有点类似dp一样的形式找最大长度。

需要注意的是分界点的长度计算，我是用2分界的，那么因为开头一定是2.分界点k左边需要求1的前缀和以及[l,k]之间2的个数即 pre1[l]+aft2[l]-aft2[k+1] （+1是因为分界点就是2 不然会少算一个2），分界点k右边需要求2的后缀和以及[k,r]之间1的个数即 aft2[r+1]+pre[r]-pre[k] （+1是因为分界点是2，不然会多算一个2（比方说数据里全是2）），然后找到最大的就行了。（这个真的很操蛋，一定要在草稿纸上模拟清楚），以下是改了一个多小时的成果：

#include<bits/stdc++.h>

using namespace std;

int a[2005],pre1[2005],aft2[2005];
int n;

int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        pre1[i]=pre1[i-1]+(a[i]==1);
    }
    for(int i=n; i>=1; i--)
        aft2[i]=aft2[i+1]+(a[i]==2);
    int ans=0;
    int kk,s1,s2;
    for(int k=1; k<=n; k++)
    {
        int sum1=0,sum2=0;
        for(int l=1; l<=k; l++) sum1=max(sum1,pre1[l]+aft2[l]-aft2[k+1]);
        for(int r=k; r<=n; r++) sum2=max(sum2,aft2[r]+pre1[r]-pre1[k]);
        ans=max(ans,sum1+sum2);
        /*if(ans<sum1+sum2)
        {
            ans=sum1+sum2;
            kk=k;
            s1=sum1;
            s2=sum2;
        }*/
    }
    //cout<<s1<<" "<<s2<<" "<<kk<<endl;
    cout<<ans<<endl;
    return 0;
}

View Code