飞机票：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19219

题意：给你一个长度为n的序列，求最长的奇数长度，使前k+1严格递增，后k+1个严格递减

分析：两次LIS 复杂度(n*logn+n*logn)=n*logn

先根据LIS求出1~n每个位置的最长递增序列长度，这里从1至n计算,然后求n~1各位置的最长序列长度，这里从n至1计算，为了不增加编码长度，可以把序列倒转，然后再求一遍，然后比较每个位置左边和右边最长序列的最小值，然后乘以2-1，每次更新MAX，最后的MAX就是最长的符合要求的长度了，这里我用了bi[0]和bi[1]两个数组，其中bi[0]是从1~n的，bi[1]是从n~1的，那么每次更新的话，就是bi[i]和bi[n-i+1]（原始位置的右边）然后取最小，MIN*2-1即可，更新MAX，OK了~啪啪啪。就可以AC了

/*
Author:Chieh
Because of You
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
const int maxn=12345;
int ai[maxn],ans[maxn],n,bi[2][maxn],sw[maxn];
int len;
void init()
{
    for(int i=1; i<=n; i++)scanf("%d",&ai[i]);
}
int brsearch(int x)
{
    int left=0,right=len;
    while(left<right)
    {
        int   mid = left+(right-left)/2;
        if(ans[mid]>=x) right=mid;
        else left=mid+1;
    }
    return left;
}
void CalLIS(int status)
{
    ans[1] = ai[1];
    bi[status][1]=1;
    len=1;
    for(int i=2; i<=n; i++)
    {
        if(ai[i]>ans[len])
        {
            ans[++len]=ai[i];
            bi[status][i]=len;
        }
        else
        {
            int pos=brsearch(ai[i]);
            ans[pos] = ai[i];
            bi[status][i]=pos;
        }
    }
}
void play()
{
    CalLIS(0);
    for(int i=1; i<=n; i++)
        sw[i]=ai[n-i+1];
    for(int i=1; i<=n; i++)
        ai[i]=sw[i];
    CalLIS(1);
    int MAX=0;
    for(int i=1; i<=n; i++)
    {
        int p=min(bi[0][i],bi[1][n-i+1]);
        MAX=max(p*2-1,MAX);
    }
    printf("%d\n",MAX);

}
int main()
{

    while(scanf("%d",&n)!=EOF)
    {
        init();
        play();
    }
    return 0;
}