#include using namespace std; #define rep(i,n) for(ll i=0;i<(n);++i) using ll = long long; using pll = pair; constexpr ll INF = (1LL<<60); constexpr ll MOD = (1e9+7); //constexpr ll MOD = (998244353); template bool chmax(T &a,const T &b){if(a bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;} void dump(){cout< void dump(T&& h, Ts&&... t){cout<(t)...);} template istream &operator>>(istream&is,vector&v){for(auto &elemnt:v)is>>elemnt;return is;} template istream &operator>>(istream&is,pair&p){is>>p.first>>p.second;return is;} templatevector make_vector(size_t a){return vector(a);} templateauto make_vector(size_t a, Ts... ts){return vector(ts...))>(a, make_vector(ts...));} void solve1();void solve2();void solve3(); int main(){ solve3(); return 0; } void solve3(){ ll n;cin>>n; vector a(n); cin>>a; vector dp(2*n); rep(i,n-1){ ll t=0; if(i>0&&a[i]==a[i+1])chmax(t,dp[i]); if(i-1>=0)chmax(t,dp[i-1]); if(i-2>=0)chmax(t,dp[i-2]); dp[i+1]=t+1; } dp[n]=max(dp[n-1],dp[n-2])+1; cout<<(*max_element(dp.begin(),dp.end()))< class segtree { private: ll n=1; T unit; std::vector dat; std::function func; public: segtree(){} segtree(std::vector a,T v,std::function f){ build(a,v,f); } void build(std::vector& a,T v,std::function f){ ll sz=a.size(); unit=v; func=f; while(n=0;--i){ dat[i]=func(dat[i*2+1],dat[i*2+2]); } } void update(ll idx,T val){ idx+=n-1; dat[idx]=val; while(idx){ idx--;idx>>=1LL; dat[idx]=func(dat[idx*2+1],dat[idx*2+2]); } } T query(ll a,ll b,ll k=0,ll l=0,ll r=-1){ if(r<0)r=n; if( b<=l || r<=a )return unit; if( a<=l && r<=b )return dat[k]; else{ auto left=query(a,b,2*k+1,l,(l+r)/2); auto right=query(a,b,2*k+2,(l+r)/2,r); return func(left,right); } } }; void solve2(){ ll n; cin>>n; vector a(n); cin>>a; vector b; ll cnt=1; rep(i,n-1){ if(a[i]!=a[i+1]){ b.emplace_back(cnt); cnt=1; }else{ cnt++; } } b.emplace_back(cnt); ll m = b.size(); vector dp(m+1); segtree seg(vector(m+1),0,[](auto a,auto b){return max(a,b);}); dp[1]=b[0]; seg.update(1,b[0]); for(ll i=2;i<=m;++i){ dp[i]=max(dp[i-1],seg.query(0,i-1)+b[i-1]); seg.update(i,dp[i]); } cout<<(seg.query(0,m+1))<>n; vector a(n); cin>>a; vector b; ll cnt = 1; rep(i,n-1){ if(a[i]!=a[i+1]){ b.emplace_back(cnt); cnt=1; }else{ cnt++; } } b.emplace_back(cnt); auto indexed = [](vectorconst& v){ vector a(v.size()); rep(i,v.size())a[i]={v[i],i}; return a; }; segtree seg(indexed(b),pll(0ll,0ll),[](auto a,auto b){return max(a,b);}); ll ans = 0; ll m = b.size(); while(1){ ll val,idx; tie(val,idx)=seg.query(0,m); if(val==0)break; ans += val; seg.update(idx,pll(0ll,0ll)); if(idx>0)seg.update(idx-1,pll(0ll,0ll)); if(idx+1