$O(nlogV+nlogn)$，但是大常数Splay+线段树（

本地测大概差个半秒左右，求卡常/kel

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1000010; 
const int N=maxn<<2;
const int inf=1e9;
inline ll read(){
	ll x=0;
	char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
struct Node{
	int l,r,k;
}q1[maxn],q2[maxn];
bool cmp(Node a,Node b){return a.l<b.l;}
bool cmp0(int a,int b){return q1[a].k<q1[b].k;}
bool cmp1(int a,int b){return q2[a].k<q2[b].k;}
int L1[maxn],R1[maxn];
int L2[maxn],R2[maxn];
int st[maxn],top;
ll c[maxn],ans;
int b[maxn],n,m;
int tot[N],data[N][2],lz[N][2];
vector<int>v[2];
int fa[2][maxn],son[2][maxn][2],a[2][maxn],cnt[2],rt[2];
void Rotate(int k,int x){
	int y=fa[k][x],z=fa[k][y],t=(son[k][y][1]==x);
	son[k][z][son[k][z][1]==y]=x,fa[k][x]=z;
	son[k][y][t]=son[k][x][!t],fa[k][son[k][x][!t]]=y;
	son[k][x][!t]=y,fa[k][y]=x,fa[k][0]=son[k][0][0]=son[k][0][1]=0;
}
void Splay(int k,int x){
	if(!x) return ;
	int y,z;
	while(fa[k][x]){
		y=fa[k][x],z=fa[k][y];
		if(z) (son[k][y][1]==x)^(son[k][z][1]==y)?Rotate(k,x):Rotate(k,y);
		Rotate(k,x);
	}
	rt[k]=x;
}
bool Com(int k,int x,int y){return k?(q2[x].k>q2[y].k):(q1[x].k>q1[y].k);}
void Insert(int k,int x){
	if(!rt[k]){
		a[k][++cnt[k]]=x,rt[k]=cnt[k];
		return ;
	}
	int t=rt[k];bool fl;
	while(son[k][t][fl=(k?(q2[x].k>q2[t].k):(q1[x].k>q1[t].k))]) t=son[k][t][fl];
	son[k][t][fl]=++cnt[k],a[k][cnt[k]]=x,fa[k][cnt[k]]=t;
	Splay(k,cnt[k]);
}
void Erase(int k){
	int t=rt[k],tm;
	while(son[k][t][0]) t=son[k][t][0];
	tm=fa[k][t];
	fa[k][son[k][t][1]]=tm,son[k][tm][0]=son[k][t][1];
	fa[k][t]=0,fa[k][0]=son[k][0][0]=son[k][0][0]=0;
	Splay(k,tm);
	if(rt[k]==t) rt[k]=son[k][t][1];
}
int Least(int k){
	if(!rt[k]) return 0;
	int t=rt[k];
	while(son[k][t][0]) t=son[k][t][0];
	Splay(k,t);return a[k][t];
}
int pc(ll x,int sum=0){
	while(x) sum+=(x&1),x>>=1;
	return sum;
}
void pushdown(int i,int l,int r,int k){
	if(lz[i][k]==-1) return ;
	int mid=l+r>>1;
	data[i<<1][k]=(lz[i][k]?mid-l+1:0);
	data[i<<1|1][k]=(lz[i][k]?r-mid:0);
	lz[i<<1][k]=lz[i<<1|1][k]=lz[i][k];
	if(lz[i][k]) 
		tot[i<<1]=data[i<<1][!k],tot[i<<1|1]=data[i<<1|1][!k];
	else tot[i<<1]=tot[i<<1|1]=0;
	lz[i][k]=-1;
}
void clear(int i,int l,int r){
	data[i][0]=data[i][1]=0;
	lz[i][0]=lz[i][1]=-1,tot[i]=0;
	if(l>r||l==r) return ;
	int mid=l+r>>1;
	clear(i<<1,l,mid),clear(i<<1|1,mid+1,r);
}
void Add(int i,int l,int r,int L,int R,int k){
	if(l>=L&&r<=R){
		lz[i][k]=1,data[i][k]=r-l+1;
		tot[i]=data[i][!k];
		return ;
	}
	int mid=l+r>>1;
	pushdown(i,l,r,0),pushdown(i,l,r,1);
	if(mid>=L) Add(i<<1,l,mid,L,R,k);
	if(mid<R) Add(i<<1|1,mid+1,r,L,R,k);
	data[i][k]=data[i<<1][k]+data[i<<1|1][k];
	tot[i]=tot[i<<1]+tot[i<<1|1];
}
void Del(int i,int l,int r,int L,int R,int k){
	if(l>=L&&r<=R){
		lz[i][k]=tot[i]=data[i][k]=0;
		return ;
	}
	int mid=l+r>>1;
	pushdown(i,l,r,0),pushdown(i,l,r,1);
	if(mid>=L) Del(i<<1,l,mid,L,R,k);
	if(mid<R) Del(i<<1|1,mid+1,r,L,R,k);
	data[i][k]=data[i<<1][k]+data[i<<1|1][k];
	tot[i]=tot[i<<1]+tot[i<<1|1];
}
bool vis[maxn];
int main(){
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) 
		c[i]=read(),m=max(m,b[i]=pc(c[i])),vis[b[i]]=1;
	for(int i=1;i<=n;i++){
		while(top&&c[st[top]]>=c[i])
			R1[st[top--]]=i-1;
		L1[i]=st[top]+1,st[++top]=i;
	}
	while(top) R1[st[top--]]=n;
	for(int i=1;i<=n;i++){
		while(top&&c[st[top]]<=c[i])
			R2[st[top--]]=i-1;
		L2[i]=st[top]+1,st[++top]=i;
	}
	while(top) R2[st[top--]]=n;
	q1[0].k=q2[0].k=inf;
	for(int t=0;t<=m;t++){
		if(!vis[t]) continue;
		int cn=0,ii1=1,ii2=1,e1=0,e2=0;
		memset(lz,-1,sizeof(lz)),memset(data,0,sizeof(data));
		memset(tot,0,sizeof(tot)),rt[0]=rt[1]=0;
		for(int i=1;i<=cnt[0];i++) son[0][i][0]=son[0][i][1]=fa[0][i]=0;
		for(int i=1;i<=cnt[1];i++) son[1][i][0]=son[1][i][1]=fa[1][i]=0;
		cnt[0]=cnt[1]=0;
		for(int i=1;i<=n;i++)
			if(b[i]==t){
				q1[++cn]=Node{L1[i],R1[i],i};
				q2[cn]=Node{L2[i],R2[i],i};
			}
		if(cn==1){ans++;continue;}
		sort(q1+1,q1+1+cn,cmp),sort(q2+1,q2+1+cn,cmp);
		q1[cn+1].l=q2[cn+1].l=inf;
		for(int l=min(q1[ii1].l,q2[ii2].l),ps,x;l<=n&&e1<cn&&e2<cn;l=ps){
			while(q1[x=Least(0)].k<l){
				Del(1,1,n,q1[x].k,q1[x].r,0);
				Erase(0),e1++;
			}
			while(q2[x=Least(1)].k<l){
				Del(1,1,n,q2[x].k,q2[x].r,1);
				Erase(1),e2++;
			}
			while(ii1<=cn&&q1[ii1].l<=l){
				Add(1,1,n,q1[ii1].k,q1[ii1].r,0);
				Insert(0,ii1),ii1++;
			}
			while(ii2<=cn&&q2[ii2].l<=l){
				Add(1,1,n,q2[ii2].k,q2[ii2].r,1);
				Insert(1,ii2),ii2++;
			}
			ps=min(min(q1[ii1].l,q2[ii2].l),min(q1[Least(0)].k+1,q2[Least(1)].k+1));
			ans+=(ps-l)*tot[1];
		}
	}
	printf("%lld\n",ans);
	return 0;
}