UVA 10534

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

ll arr[10000];
set<ll> arr_c;
ll f[10000];
ll b[10000];

ll nodes[50000];
int n;

void build(int l = 0, int r = n-1, int p = 1) {
    if(l == r) {
        nodes[p] = 0;
    }
    else {
        int mid = (r+l)/2;
        build(l,mid,p*2);
        build(mid+1,r,p*2+1);
        nodes[p] = 0;
    }
}

ll query(int ql, int qr, int l = 0, int r = n-1, int p = 1) {
    if(l >= ql && r <= qr) {
        return nodes[p];
    }
    if(qr < l || ql > r) {
        return 0;
    }
    int mid = (r+l)/2;
    return max(query(ql,qr,l,mid,p*2),query(ql,qr,mid+1,r,p*2+1));
}

void update(int qt, ll qv, int l = 0, int r = n-1, int p = 1) {
    if(l == r) {
        nodes[p] = max(qv,nodes[p]);
    }
    else {
        int mid = (l+r)/2;
        if(qt <= mid) {
            update(qt,qv,l,mid,p*2);
        }
        else {
            update(qt,qv,mid+1,r,p*2+1);
        }
        nodes[p] = max(nodes[p*2],nodes[p*2+1]);
    }
}

map<ll,ll> mp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while(cin >> n) {
    //for(int ti = 0; ti < 75; ti++) {
        //n = 10000;
        arr_c.clear();
        mp.clear();
        for(int i = 0; i < n; i++) {
            cin >> arr[i];
            //arr[i] = (i < n/2 ? i:n-i);
            arr_c.insert(arr[i]);
        }
        int idx = 0;
        for(int v : arr_c) {
            mp[v] = idx++;
        }
        for(int i = 0; i < n; i++) {
            arr[i] = mp[arr[i]];
        }
        build();
        for(int i = 0; i < n; i++) {
            if(!arr[i]) {
                f[i] = 1;
            }
            else {
                f[i] = 1+query(0,arr[i]-1);
            }
            update(arr[i],f[i]);
        }
        build();
        //memset(nodes,0,sizeof(nodes));
        for(int i = n-1; i >= 0; i--) {
            if(!arr[i]) {
                b[i] = 1;
            }
            else {
                b[i] = 1+query(0,arr[i]-1);
            }
            update(arr[i],b[i]);
        }
        ll ans = 1;
        /*cout << "arr is: ";
        for(int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";*/
        for(int i = 0; i < n; i++) {
            if(!f[i] || !b[i])
                continue;
            //cout << " at i = " << i << " l = " << f[i] << " r = " << b[i] << "\n";
            ans = max(ans,1+min(f[i]-1,b[i]-1)*2);
        }
        cout << ans << "\n";
    }
    return 0;
}