Codeforces 1053 B - Vasya and Good Sequences

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int M=1e6+5;
ll a[10],countt[M];
int main(){
    ll ans=0;
    int n;
    scanf("%d",&n);
    int sign=0;
    a[0]=1;
    for(int i=1;i<=n;i++){
        ll x;
        scanf("%I64d",&x);
        int t=0;
        while(x){
            if(x&1)
                t++;
            x>>=1;
        }
        countt[i]=countt[i-1]+t;
        sign^=t&1;
        ans+=a[sign];
        ll maxx=0;
        for(int j=i;i-j<=64&&j>=1;j--){
            maxx=max(maxx,countt[j]-countt[j-1]);
            if((countt[i]-countt[j-1])%2==0&&2*maxx>countt[i]-countt[j-1])
                ans--;
        }
        a[sign]++;
    }
    printf("%I64d",ans);
    return 0;
}