UVA 10534 - Wavio Sequence

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
main()
{
    long n;
    while(cin>>n)
    {
        long i,ar[10006]= {0};
        vector<long>vec;
        long lis[10006],x=0,low=0,lds[10006];
        for(i=0; i<n; i++)
        {
            cin>>ar[i];
        }
        lis[0]=1,x=1;
        vec.push_back(ar[0]);
        for(i=1;i<n;i++)
        {
            if(ar[i]>vec.back())
            {
                vec.push_back(ar[i]);
                lis[i]=++x;
            }
            else
            {
                low=lower_bound(vec.begin(),vec.end(),ar[i])-vec.begin();
                vec[low]=ar[i];
                lis[i]=low+1;
            }
        }
        vec.clear();
        lds[n-1]=1;
        x=1;
        vec.push_back(ar[n-1]);
        for(i=n-2;i>=0;i--)
        {
            if(ar[i]>vec.back())
            {
                vec.push_back(ar[i]);
                lds[i]=++x;
            }
            else
            {
                low=lower_bound(vec.begin(),vec.end(),ar[i])-vec.begin();
                vec[low]=ar[i];
                lds[i]=low+1;
            }
        }
        long mn,mx=0;
        for(i=0;i<n;i++)
        {
           // cout<<lis[i]<<" "<<lds[i]<<endl;
            mn=min(lis[i],lds[i]);
            mx=max(mx,mn);
        }
        //cout<<mx<<endl;
        cout<<2*mx-1<<endl;
    }
}