如果一个序列有奇数个正整数组成，不妨令此序列为a 1 ,a 2 ,a 3 ,...,a 2∗k+1   (0<=k  )，并且a 1 ,a 2 ...a k+1   是一个严格递增的序列，a k+1 ,a k+2 ,...,a 2∗k+1   ,是一个严格递减的序列，则称此序列是A序列。

比如1 2 5 4 3就是一个A序列。

现在Jazz有一个长度为n  的数组，他希望让你求出这个数组所有满足A序列定义的子序列里面最大的那个长度。（子序列可以不连续）

比如1 2 5 4 3 6 7 8 9，最长的A序列子串是1 2 5 4 3。

#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>

#include<cstdio>

#include<vector>

#include<queue>

#include<cstring>

#include<string>

#include<stack>

#include<algorithm>

using namespace std;

#define INF 0x3f3f3f3f

const int N_MAX = +;

vector<int>vec;

int dp[N_MAX];

int Right[N_MAX], Left[N_MAX];

int n;

void LIS(const vector<int>&vec,int *a) {

    fill(dp,dp+n,INF);

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

        *lower_bound(dp,dp+n,vec[i])=vec[i];

        a[i] = lower_bound(dp, dp + n, INF) - dp;

    }

}

int main() {

    while (scanf("%d",&n)!=EOF) {

        vec.clear();

        vec.resize(n);

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

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

        int ans=;

        LIS(vec,Left);

        reverse(vec.begin(), vec.end());

        LIS(vec, Right);

        int res=;

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

            int ans = min(Right[i], Left[n-i]);

            res = max(res, ans);

        }

        printf("%d\n",*res-);

    }

    return ;

}