UVa 10534 - Wavio Sequence

// Accepted

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>

#define sf scanf
#define pf printf
#define high 10010

using namespace std;

typedef long long LL;

const LL inf = 2147483648;

int n;
LL seq[high] , I[high], L1[high] , L2[high];

void LIS()
{
    int i, j;
    LL len=0;

    I[0] = -inf;

    for(i=1; i<=n; i++)
    {
        I[i] = inf;
    }

    for(i=0; i<n; i++)
    {
        int lo=0, hi=len, mid;

        while(lo <= hi)
        {
            mid = (lo + hi) / 2;

            if(I[mid] < seq[i])
            {
                lo = mid+1;
            }

            else
            {
                hi = mid - 1;
            }
        }

        I[lo] = seq[i];
        L1[i] = lo;

        if(len < lo)
        {
            len = lo;
        }
    }
}

void LDS()
{
    int i,j;
    LL len = 0;

    I[0] = -inf;

    for(i=1; i<=n; i++)
    {
        I[i] = inf;
    }

    for(i=n-1; i>=0; i--)
    {
        int lo=0, hi=len, mid;

        while(lo <= hi)
        {
            mid = (lo + hi) / 2;

            if(I[mid] < seq[i])
            {
                lo = mid + 1;
            }

            else
            {
                hi = mid - 1;
            }
        }

        I[lo] = seq[i];
        L2[i] = lo;

        if(len < lo)
        {
            len = lo;
        }
    }
}

int main()
{
    //freopen("out.txt" , "w" , stdout);

    while(~sf("%d",&n)){

    int i;

    for(i=0; i<n; i++)
    {
        sf("%lld",&seq[i]);
    }

    LIS();
    LDS();
    //for(i=0; i<n; i++) cout << L1[i] << " ";
    //cout << "\n";
    //for(i=0; i<n; i++) cout << L2[i] << " ";
    LL ans=1;

    for(i=0; i<n; i++)
    {
        ans = max(ans , min(L1[i] , L2[i]));
    }

    pf("%lld\n" , (ans * 2) - 1);

    }

    return 0;
}