cf round480D Perfect Groups

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=5000+7,M=120;
ll n,a[maxn],nxt[maxn],ans[maxn];
set<ll> prime;
set<ll>::iterator it;

char cc;ll ff;
template<typename T>void read(T& aa) {
	aa=0;ff=1; cc=getchar();
	while(cc!=‘-‘&&(cc<‘0‘||cc>‘9‘)) cc=getchar();
	if(cc==‘-‘) ff=-1,cc=getchar();
	while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar();
	aa*=ff;
}

ll qp(ll x,ll k,ll mod) {
	ll rs=1;
	while(k) {
		if(k&1) rs=rs*x%mod;
		k>>=1; x=x*x%mod;
	}
	return rs;
}

ll gcd(ll x,ll y) {return y==0? x:gcd(y,x%y);}

bool isprime(ll n) {
	if(n==2||n==3||n==5||n==7) return 1;
	if(n<2||(n%6!=1&&n%6!=5)) return 0;
	ll m=n-1,t=0,x,y;
	while((m&1)==0) t++,m>>=1;
	For(qaq,1,20) {
		x=rand()%(n-2)+2;
		x=qp(x,m,n);
		For(i,1,t) {
			y=x*x%n;
			if(y==1&&x!=1&&x!=n-1) return 0;
			x=y;
		}
		if(x!=1) return 0;
	}
	return 1;
}

ll prho(ll n,ll m) {
	ll x=rand()%(n-1)+1,y=0;
	for(ll i=1,k=1,d;y!=x;++i) {
		if(i==k) {y=x;k<<=1;}
		x=(x*x+m)%n;
		d=gcd((y-x+n)%n,n);
		if(d>1&&d<n) return d;
	}
	return n;
}

void find(ll n,ll m) {
	if(isprime(n)) {
		it=prime.find(n);
		if(it==prime.end()) prime.insert(n);
		else prime.erase(it);
		return;
	}
	ll p=n; while(p>=n) p=prho(n,m--);
	find(p,M); find(n/p,M);
}

ll get_num(ll n) {
//	cerr<<"get_num("<<n<<")\n";
	if(n==1||n==0) return n;
	find(n,M);
	ll rs=1;
	while(!prime.empty()) {
		it=prime.begin();
		rs*=*it;
		prime.erase(it);
	}
	return rs;
}

int main() {
	read(n); ll x;
	For(i,1,n) {
//		cerr<<"get a["<<i<<"]:";
		read(x);
		a[i]=get_num(abs(x));
		if(x<0) a[i]=-a[i];
	}
	For(i,1,n) {
		nxt[i]=n+1;
		For(j,i+1,n) if(a[j]==a[i]) {nxt[i]=j;break;}
	}
	int now;
	For(i,1,n) {
		now=0;
		Rep(j,i,1) {
			if(a[j]&&nxt[j]>i) ++now;
			++ans[now];
		}
	}
	ans[1]+=ans[0];
	For(i,1,n) printf("%lld ",ans[i]);
	printf("\n");
	return 0;
}