Source Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define mk make_pair
#define pb push_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;

ll mod = 998244353 ;

typedef tree<int, null_type, less_equal<int>,
            rb_tree_tag,
            tree_order_statistics_node_update>
    ordered_set;
ll fact[200001] ;
ll mul(ll a , ll b){
    return a * b % mod ;
}
ll power(ll a , ll b){
    ll ans = 1 , cur = a;
    while(b){
        if(b%2) ans *= cur ;
        cur *= cur ;
        cur %= mod ;
        ans %= mod ;
        b /= 2;
    }
    return ans % mod ;
}
ll divide(ll a , ll b){
    return mul(a , power(b , mod - 2)) % mod ;
}
ll nck(ll a , ll b){
    return divide(fact[a] , fact[b] * fact[a-b] % mod) % mod ;
}

const int N = 2e5 + 1 ;


void solve(){

    int n ;
    cin >> n ; n--;
    vector<int> v(n) ;
    vector<vector<int> > p , p2 ;
    vector<int> temp;
    for(int i=0 ; i<n ; i++){
        cin >> v[i];
        if(v[i] == 0){
            if(temp.size() > 0) p.pb(temp);
            temp.clear();
        }
        else{
            temp.pb(v[i]);
        }
    }
    if(temp.size() > 0) p.pb(temp) , temp.clear();
    for(int i=0 ; i<p.size() ; i++){
        for(int j=0 ; j<p[i].size() ; j++){
            if(j == 0) temp.pb(p[i][j] % 2) ;
            else if(p[i][j] % 2 != p[i][j-1] % 2) temp.pb(p[i][j] % 2) ;
        }
        p2.pb(temp);
        temp.clear();
    }


    int ans = 0 ;
    for(int i=0 ; i<p2.size() ; i++){
        if(p2[i].size() == 1) continue ;
        if(p2[i].size() % 2 == 0){
            ans += (p2[i].size() / 2 - 1) ;
        }
        else{
            if(p2[i][0] == 0) ans += (p2[i].size() / 2 - 1) ;
            else ans += p2[i].size() / 2 ;
        }
    }
    ans += (p2.size() - 1);
    cout << ans ;

}
int main() {

    int t = 1 ;
    //cin >> t ;
    while(t--){
        solve();
    }


	return 0;
}
Copy
Teleportation Tuff1aha
GNU G++17
91 ms
11.5 MB
Accepted