#include using namespace std; #define SEG_TREE_SIZE 500000 #define NONE -1 #define DEBUG if(0) typedef long long LL; #define cp(x) x=o.x #define INF 100010 struct INIT{INIT(){ios::sync_with_stdio(false);cin.tie(0);}}init; vector used(SEG_TREE_SIZE,true); struct V{ int id,v,prev; V(int id,int v,int prev):id(id),v(v),prev(prev){} void print(){printf("(id=%d,v=%d,prev=%d)\n",id,v,prev);} }; class ND{ public: pair fs; ND():fs(V(0,-1,INF),V(0,-1,INF+1)){}; ND(int id):fs(V(id,0,INF),V(id,0,INF+1)){}; ND& copy(const ND& o){cp(fs);return *this;} ND& operator=(const ND& o){return copy(o);} ND operator+(const ND& o){ ND res; auto fupdate=[&](const V& v){ if(res.fs.first.v class node{ public: int bg,ed,L,R; T val,add_val,lazy_val; bool val_update,add_update; node():bg(NONE),ed(NONE),L(NONE),R(NONE),val(),add_val(),lazy_val(),val_update(false),add_update(false){} node(int bg,int ed,int L,int R):bg(bg),ed(ed),L(L),R(R),val(),add_val(),lazy_val(),val_update(false),add_update(false){} node(int bg,int ed,int L,int R,T val):bg(bg),ed(ed),L(L),R(R),val(val),add_val(),lazy_val(),val_update(false),add_update(false){} node(int bg,int ed,int L,int R,T val,T add_val):bg(bg),ed(ed),L(L),R(R),val(val),add_val(add_val),lazy_val(),val_update(false),add_update(false){} void set(T v){val_update=true,lazy_val=v;} void add(T v){add_update=true,add_val=add_val+v;} void update_clear(){val_update=add_update=false,add_val=lazy_val=T();} //T get(){return val+(add_val+lazy_val)*len();} T get(){return val+add_val+lazy_val;} int len(){return ed-bg+1;} node& copy(const node& o){cp(bg),cp(ed),cp(L),cp(R),cp(val),cp(add_val),cp(lazy_val),cp(val_update),cp(add_update);return *this;} node& operator=(const node& o){return copy(o);} bool isleaf(){return bg>=ed;} bool iscontain(int l,int r){return bg<=l&&r<=ed;} bool isequal(int l,int r){return l==bg&&r==ed;} void print(){ printf("[%d-%d]updates(%d,%d)\n",bg,ed,(int)val_update,(int)add_update); get().print(); } }; node _seg_prepared_table[1]; /**/ template inline T merge(node &l,node &r){return l.get()+r.get();} template inline T merge(T &l,node &r){return l+r.get();} template class segtree{ private: using NODE=node; int begin,end; stack st1,stL,stR,rollback; NODE *t; inline void lazy_update(NODE& now){ if(now.isleaf())return; if(now.val_update){t[now.L].set(now.lazy_val);t[now.R].set(now.lazy_val);} if(now.add_update){t[now.L].add(now.add_val);t[now.R].add(now.add_val);} now.update_clear(); } void all_update(){ while(rollback.empty()==false){ auto& now=t[rollback.top()];rollback.pop(); if(!now.isleaf())now.val=merge(t[now.L],t[now.R]); } } public: segtree():begin(0),end(0),t(_seg_prepared_table){} segtree(int bg,int ed,NODE* t):begin(bg),end(ed),t(t){ int sz=0; t[0]=NODE(bg,ed,sz+1,sz+2);sz+=2; st1.push(0); while(st1.empty()==false){ int id=st1.top();st1.pop();rollback.push(id); auto& now=t[id]; if(now.isleaf()){now.val=T(now.bg);continue;} int half=(now.bg+now.ed)/2; t[now.L]=NODE(now.bg,half,sz+1,sz+2);sz+=2; t[now.R]=NODE(half+1,now.ed,sz+1,sz+2);sz+=2; st1.push(now.L);st1.push(now.R); } all_update(); } //遅延評価対応,値の書き換え void segment_set(int bg,int ed,T v){ if(!t[0].iscontain(bg,ed)){printf("query=(segment_set,%d,%d) ERROR\n",bg,ed);exit(-1);} auto PUSH=[&](int id,int l,int r){st1.push(id),stL.push(l),stR.push(r);}; auto POP=[&](int& id,int &l,int &r){id=st1.top(),l=stL.top(),r=stR.top();st1.pop(),stL.pop(),stR.pop();}; PUSH(0,bg,ed); while(st1.empty()==false){ int id,L,R; POP(id,L,R);rollback.push(id); auto &now=t[id]; lazy_update(now); if(now.isequal(L,R)){now.set(v);continue;} if(t[now.L].iscontain(L,R))PUSH(now.L,L,R); else if(t[now.R].iscontain(L,R))PUSH(now.R,L,R); else {PUSH(now.L,L,t[now.L].ed);PUSH(now.R,t[now.R].bg,R);} } all_update(); } void set(int pos,T v){ segment_set(pos,pos,v); } void segment_add(int bg,int ed,T v){ if(!t[0].iscontain(bg,ed)){printf("query=(segment_add,%d,%d) ERROR\n",bg,ed);exit(-1);} auto PUSH=[&](int id,int l,int r){st1.push(id),stL.push(l);stR.push(r);}; auto POP=[&](int& id,int &l,int &r){id=st1.top(),l=stL.top(),r=stR.top();st1.pop(),stL.pop(),stR.pop();}; PUSH(0,bg,ed); while(st1.empty()==false){ int id,L,R; POP(id,L,R);rollback.push(id); auto &now=t[id]; lazy_update(now); if(now.isequal(L,R)){now.add(v);continue;} if(t[now.L].iscontain(L,R))PUSH(now.L,L,R); else if(t[now.R].iscontain(L,R))PUSH(now.R,L,R); else {PUSH(now.L,L,t[now.L].ed);PUSH(now.R,t[now.R].bg,R);} } all_update(); } T get(int bg,int ed){ T res=T(); auto PUSH=[&](int id,int l,int r){st1.push(id),stL.push(l),stR.push(r);}; auto POP=[&](int& id,int &l,int &r){id=st1.top(),l=stL.top(),r=stR.top(),st1.pop(),stL.pop(),stR.pop();}; PUSH(0,bg,ed); while(st1.empty()==false){ int id,L,R; POP(id,L,R);rollback.push(id); auto &now=t[id]; if(now.isequal(L,R)){res=merge(res,now);continue;} lazy_update(now); if(t[now.L].iscontain(L,R))PUSH(now.L,L,R); else if(t[now.R].iscontain(L,R))PUSH(now.R,L,R); else {PUSH(now.L,L,t[now.L].ed);PUSH(now.R,t[now.R].bg,R);} } all_update(); return res; } }; node _u[SEG_TREE_SIZE],_d[SEG_TREE_SIZE]; int main(){ int res=0; segtree up(0,INF+1,_u); segtree down(0,INF+1,_d); int N;cin>>N; vector Q(N); map m; for(auto& it : Q){ cin>>it; m[it]=0; } {int t=2;for(auto& it : m)it.second=t++;} for(auto& it : Q){ int h=m[it]; ND U,D; { auto u=up.get(h+1,INF-2); if(u.fs.first.prev!=h)U.fs.first=u.fs.first; else U.fs.first=u.fs.second; u=up.get(U.fs.first.id+1,INF-1); if(U.fs.first.id!=h+1)u=u+up.get(h+1,U.fs.first.id-1); if(u.fs.first.prev!=h)U.fs.second=u.fs.first;else U.fs.second=u.fs.second; U.fs.first.v++;U.fs.second.v++; U.fs.first.prev=U.fs.first.id;U.fs.second.prev=U.fs.second.id; U.fs.first.id=U.fs.second.id=h; } { auto d=down.get(1,h-1); if(d.fs.first.prev!=h)D.fs.first=d.fs.first; else D.fs.first=d.fs.second; d=down.get(0,D.fs.first.id-1); if(D.fs.first.id!=h-1)d=d+down.get(D.fs.first.id+1,h-1); if(d.fs.first.prev!=h)D.fs.second=d.fs.first;else D.fs.second=d.fs.second; D.fs.first.v++;D.fs.second.v++; D.fs.first.prev=D.fs.first.id;D.fs.second.prev=D.fs.second.id; D.fs.first.id=D.fs.second.id=h; } down.set(h,U); up.set(h,D); res=max(res,U.fs.first.v); res=max(res,D.fs.first.v); } if(res<3)cout<<0<