#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC push_options #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #include #include #include using namespace::std; __attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout< #include #include #include // #include // #include // namespace mp = boost::multiprecision; // typedef mp::number> cdouble; // typedef mp::cpp_int cint; templateinline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<inline void output2(T t){for(auto i:t)output(i);} templateinline void debug(T t){bool f=0;for(auto i:t){cerr<<(f?" ":"")<inline void debug2(T t){for(auto i:t)debug(i);} templateusing pbds=__gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; templateusing pbds_map=__gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; templateusing hash_map=__gnu_pbds::gp_hash_table; templateusing pqueue =__gnu_pbds::priority_queue,__gnu_pbds::rc_binomial_heap_tag>; typedef long long lint; #define INF (1LL<<60) #define IINF (1<<30) #define LINF (9223372036854775807LL) #define EPS (1e-10) #define endl ('\n') //#define MOD 1000000007LL #define MOD 998244353LL //#define MOD 1000000000039LL typedef vector vec; typedef vector> mat; typedef vector>> mat3; typedef vector svec; typedef vector> smat; #define rep(i,...) for(auto i:range(__VA_ARGS__)) #define rrep(i,...) for(auto i:reversed(range(__VA_ARGS__))) #define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i) #define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i) #define irep(i) for(lint i=0;;++i) inline vector range(int64_t n){vectorv(n);iota(v.begin(),v.end(),0LL);return v;} inline vector range(int64_t a,int64_t b){vectorv(b-a);iota(v.begin(),v.end(),a);return v;} inline vector range(int64_t a,int64_t b,int64_t c){vectorv((b-a+c-1)/c);for(int i=0;i<(int)v.size();++i)v[i]=i?v[i-1]+c:a;return v;} inline auto reversed(auto v){reverse(v.begin(),v.end());return v;} #define all(n) begin(n),end(n) #define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2)) //inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;} //inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;} // inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;} // inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;} bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;} bool chmax(auto& s,const auto& t){bool res=s dx={1,0,-1,0,1,1,-1,-1}; const vector dy={0,1,0,-1,1,-1,1,-1}; #define SUM(v) accumulate(all(v),0LL) auto call=[](auto f,auto... args){return f(f,args...);}; templateauto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector(arg,x);else return vector(arg,make_vector(x,args...));} int msb(int x){return 32-__builtin_clz(x);} lint bs(lint mn,lint mx,auto func){ mn--; mx++; while(mx-mn>1){ lint mid=(mn+mx)/2; if(!func(mid))mx=mid; else mn=mid; } return mn; } int main(){ lint n; cin>>n; vec a(n); rep(i,n)cin>>a[i]; lint ans=0; rep(_,2){ vec v,l(n),r(n); rep(i,n){ auto itr=lower_bound(all(v),a[i]); if(itr==v.end())v.push_back(a[i]); else v[itr-v.begin()]=a[i]; l[i]=v.size(); } v.clear(); rrep(i,n){ auto itr=lower_bound(all(v),a[i]); if(itr==v.end())v.push_back(a[i]); else v[itr-v.begin()]=a[i]; r[i]=v.size(); } rep(i,n){ chmax(ans,min(l[i],r[i])-1); } rep(i,n)a[i]*=-1; } cout<