Co prime Array

#include <bits/stdc++.h>
using namespace std;
#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll long long int
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ull unsigned long long int
#define vll vector<ll>
#define vld vector<ld>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define vpll vector<pll>
#define vpld vector<pld>
#define all(X) X.begin(),X.end()
#define mo 1000000007
 ll lo[100005];  vector<ll> prime[100005];  vector<ll> pos[100005]; int cur[100005];

void solve()
{
   int n ; cin>>n;
   int a[n];
   lp(i,0,n)
   cin>>a[i];
  lo[0]=0; lo[1]=1;
   for(ll i =2; i<100005; i++)
   {
     if(lo[i])
     continue;
     lo[i]=i;
     for(ll j = i*i; j<100005; j+=i)
     {
     	if(lo[j]==0)
     	lo[j]=i;
	 }
   }

   for(int i = 0 ; i<n ; i++)
   {
   	ll temp = a[i];
   	while(temp>1)
   	{
   		ll curl = lo[temp];
   		pos[curl].pb(i);
   		prime[i].pb(curl);

   		while(temp%curl==0)
   		temp/=curl;
	   }
   }
    for(int i =0; i<100005;i++)
    cur[i]= pos[i].size();
	 ll ans = 0 ; ll temp = n ;
	 for(int i =n-1; i>=0; i--)
	 {
	 	for(int j =0 ; j<prime[i].size(); j++)
	 	{
	 		int p = prime[i][j];
	 		if(cur[p]==pos[p].size())
	 		{
	 			cur[p]--;
	 			continue;
			 }
	 		temp = min(temp,pos[p][cur[p]]);
	 		cur[p]--;
		 }
	   ans+=(temp-i);
     }
     cout<<ans<<endl;

}


int main()
{ ios;
	ll t;t =1 ;
	while(t--)
	{
		solve();

	}
	return(0);
}