Untitled

#include <bits/stdc++.h>
using namespace std;
long num;
vector<long > leaders;

long cal(){
    vector<long> tail1(num, 0),tail2(num, 0);
	long len1 = 1 ,len2 = 1 , len3 = 1 ,len4 = 1;
	//////////////////////////////////////////////////////////decreasing
	long floor = 0;
	tail1[0] = leaders[0];
	for (int i = 1 ; i <= num-1 ; i++) {
        auto b1f = tail1.begin(), e1f = tail1.begin() + len1;
		auto it1 = lower_bound(b1f, e1f, leaders[i] , greater<long>());
		if (leaders[i] > tail1[0]){
            tail1[0] = leaders[i];
		}
		else if (leaders[i] < tail1[len1 - 1]){
            tail1[len1++] = leaders[i];
            floor = i;
		}
		else{
            *it1 = leaders[i];
		}

	}
	tail1[0] = leaders[num-1];
	for (int i = num-2; i >= floor ; i--) {
        auto b1b = tail1.begin(), e1b = tail1.begin() + len2;
		auto it2 = lower_bound(b1b, e1b, leaders[i] , greater<long>());
		if (leaders[i] > tail1[0]){
            tail1[0] = leaders[i];
		}
		else if (leaders[i] < tail1[len2 - 1]){
            tail1[len2++] = leaders[i];
		}
		else{
            *it2 = leaders[i];
		}
	}
	/////////////////////////////////////////////////////////////increasing
	long peak = 0;
	tail2[0] = leaders[0];
	for (int i = 1 ; i <= num-1 ; i++) {
        auto b2f = tail2.begin(), e2f = tail2.begin() + len3;
		auto it3 = lower_bound(b2f, e2f, leaders[i]);
		if (leaders[i] < tail2[0]){
            tail2[0] = leaders[i];
		}
		else if (leaders[i] > tail2[len3 - 1]){
            tail2[len3++] = leaders[i];
            peak = i;
		}
		else{
            *it3 = leaders[i];
		}
	}

	tail2[0] = leaders[num-1];
	for (int i = num-2; i >= peak ; i--) {
        auto b2b = tail2.begin(), e2b = tail2.begin() + len4;
		auto it4 = lower_bound(b2b, e2b, leaders[i]);
		if (leaders[i] < tail2[0]){
            tail2[0] = leaders[i];
		}
		else if (leaders[i] > tail2[len4 - 1]){
            tail2[len4++] = leaders[i];
		}
		else{
            *it4 = leaders[i];
		}
	}
	//cout<<len1<<" "<<len2<<" "<<len3<<" "<<len4<<"\n";
	return max(len1+len2-1,len3+len4-1);
}

int main(){
	cin.tie(0);
    cin.sync_with_stdio(0);
    cin>>num;

    for(int i = 0 ; i < num ; i ++){
        long a;
        cin>>a;
        leaders.push_back(a);
    }
    cout<<cal();
	return 0;
}