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.

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).

Print a single integer, which means the maximum possible length of the longest non-decreasing subsequence of the new sequence.

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组成的序列，要求翻转一个区间，使得最长不下降子序列尽可能长.

分析：读错题坑了我40分钟.子序列可以不连续！

　　　考虑没有翻转操作.那么答案肯定是一个位置左边的1的数量+右边的2的数量,取max. 那么我们可以统计1的前缀和，2的后缀和.

　　　如果有翻转操作.其实就是翻转的区间中的一个位置统计1的后缀和，同时在这个位置统计2的前缀和，最后和两个端点处的相减.

具体来说，如果记sum1为1的前缀和，sum2为2的后缀和，sum3为1的后缀和，sum4为2的前缀和，翻转的两个区间端点为a,b.那么答案就是max{sum1[a - 1] + sum2[b + 1] + sum3[i + 1] - sum3[b + 1] + sum4[i] - sum4[a - 1]}.实际上变动的就是sum3[i + 1]与sum4[i],求出一个区间内它们的最大值，有很多方法.我偷懒用线段树维护.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

int n,a[],ans,f[][],sum1[],sum2[],sum3[],sum4[],b[],maxx[ << ];

void pushup(int o)

{

    maxx[o] = max(maxx[o * ],maxx[o *  + ]);

}

void build(int o,int l,int r)

{

    if (l == r)

    {

        maxx[o] = b[l];

        return;

    }

    int mid = (l + r) >> ;

    build(o * ,l,mid);

    build(o *  + ,mid + ,r);

    pushup(o);

}

int query(int o,int l,int r,int x,int y)

{

    if (x <= l && r <= y)

        return maxx[o];

    int mid = (l + r) >> ,res = -;

    if (x <= mid)

        res = max(res,query(o * ,l,mid,x,y));

    if (y > mid)

        res = max(res,query(o *  + ,mid + ,r,x,y));

    return res;

}

int main()

{

    scanf("%d",&n);

    for (int i = ; i <= n; i++)

        scanf("%d",&a[i]);

    for (int i = ; i <= n; i++)

        sum1[i] = sum1[i - ] + (a[i] ==  ?  : );

    for (int i = n; i >= ; i--)

        sum2[i] = sum2[i + ] + (a[i] ==  ?  : );

    for (int i = n; i >= ; i--)

        sum3[i] = sum3[i + ] + (a[i] ==  ?  : );

    for (int i = ; i <= n; i++)

        sum4[i] = sum4[i - ] + (a[i] ==  ?  : );

    for (int i = ; i <= n; i++)

        b[i] = sum4[i] + sum3[i + ];

    build(,,n);

    for (int i = ; i <= n; i++)

    {

        for (int j = i; j <= n; j++)

        {

            int temp = query(,,n,i - ,j);

            ans = max(ans,sum1[i - ] + sum2[j + ] + temp - sum3[j + ] - sum4[i - ]);

        }

    }

    printf("%d\n",ans);

    return ;

}