#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //using namespace atcoder; using namespace std; #define P pair #define Graph vector> #define float long double #define rep(i,a,b) for(int i=(a);i<(b);++i) #define repi(itr,m) for(auto itr=(m).begin();itr!=(m).end();itr++) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define vi vector #define int long long const int INF=1e18; int dx[8]={0,1,0,-1,-1,-1,1,1}; int dy[8]={1,0,-1,0,-1,1,-1,1}; template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false));} template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false));} struct point{ int x,y; }; void yn(bool t){ if(t)cout<<"Yes"<>n; vectors(n+1,1); rep(i,1,n+1){ char c;cin>>c; s[i]=c-'0'; } vectoryes(n+1,0); vectorno(n+1,0); vectorval; int idx=0; rep(i,1,n+1){ if(s[i]==0){ val.push_back(i); if(val.size()==1)idx=i; } } yes[idx]=1; rep(i,idx+1,n+1){ if(s[i]==1){ yes[i]=yes[i-1]; no[i]=no[i-1]; } else{ auto itr=lower_bound(all(val),i); itr--; idx=*itr; if(i-idx>=3){ yes[i]=min(yes[i-1],no[i-1])+1; no[i]=no[i-1]; } else{ yes[i]=min(yes[i-1],no[i-1])+1; no[i]=yes[i-1]; } } } cout<