#include #include #include #include #include #include using namespace std; using ll = long long; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin>>n; vector a(n); for(int i = 0;i>a[i]; vector> dp(n+1,vector(3,1e9)); dp[0][2] = 0; for(int i = 0;i> ndp(n+1,vector(3,1e9)); if(a[i]==2){ for(int j = 0;j<=n;j++){ ndp[j][2] = min(ndp[j][2],dp[j][0]); ndp[j][2] = min(ndp[j][2],dp[j][1]); ndp[j][2] = min(ndp[j][2],dp[j][2]); } swap(ndp,dp); continue; } for(int j = 0;j<=n;j++){ if(a[i]==0){ if(j+1<=n) ndp[j+1][0] = min(ndp[j+1][0],dp[j][0]); if(j+1<=n) ndp[j+1][0] = min(ndp[j+1][0],dp[j][2]); ndp[j][1] = min(ndp[j][1],dp[j][1]+1); ndp[j][1] = min(ndp[j][1],dp[j][2]+1); }else{ if(j+1<=n) ndp[j+1][0] = min(ndp[j+1][0],dp[j][0]+1); if(j+1<=n) ndp[j+1][0] = min(ndp[j+1][0],dp[j][2]+1); ndp[j][1] = min(ndp[j][1],dp[j][1]); ndp[j][1] = min(ndp[j][1],dp[j][2]); } } swap(ndp,dp); } int ans = 1e9; int cnt = 0; for(int i = 0;i