給定 \(n\) 和長度為 \(n\) 的正整數序列 \(a\)。
定義一次操作為，選擇一個數 \(a_i\) 和質數 \(p\)，將 \(a_i\) 賦值為 \(a_i\times p\) 或 \(\frac{a_i}{p}\)，必須滿足賦值后 \(a_i\) 為正整數。

定義區間 \(l,r\) 的代價 \(val(l,r)\) 為，使 \(a_l,a_{l+1},\cdots,a_r\) 全都相等的最小操作次數。

請求出 \(\sum_{l=1}^n \sum_{r=l}^n val(l,r)\)，對 \(10^9+7\) 取模。

對于 \(100\%\) 的數據，\(1\le n\le 2\times 10^5\)，\(1\le a_i\le 10^6\)。

口胡題解：

先轉化一下式子：

假設 \(b_i\) 為 \(a_i\) 的 \(p\) 次方,這有兩個結論：

和

那么其中 \(f\) 計算方法為：

我們設 \(sum_r=\sum^{r}_{i=1}([b_i\le k]-[b_i> k])\) 考慮在 \(p,k\) 確定的情況下，也就是 \(sum\) 確定的情況下快速計算 \(\sum^{n}_{l=1}\sum^{n}_{r=l}f(l,r,p,k)\).

考慮先對 \(sum\) 排序，前面的 \((r-l+1)\) 當成區間長度，這個求和是好做的，我們記為 \(len\)，此時我們可以把式子變成：

換個方式，就是：

這樣計算復雜度就降低了，考慮現在復雜度：發現是 \(O(Pn\log n\log V)\)，其中 \(P\) 是質數個數，算出來不超過 \(8\times 10^4\)，考慮優化。

接下來是真口胡了，我不知道具體怎么做。

看看怎么優化這個東西，因為每個數都由 \(O(\log V)\) 個質數構成，所以發現 \(sum_i\) 的非 \(+1\) 的變化次數是 \(O(\frac{n\log V}{P})\) 的。也就是說我們先給每個數 \(+i\)，那么就只有 \(O(\frac{n\log V}{P})\) 個值了，那么直接找出所有的變化點，相當于把 \(sum_i\) 加權，接著做這個式子，現在復雜度就是 \(O(n\log^2V\log(\log\frac{n\log V}{P}))\)，能過了。

官方題解：

每個質數分別計算，問題變成每次將一個數加 1 或減 1，使所有數都相等的最小操作次數。
可以發現變為中位數次數最小，考慮計算。
可能要自行腦補一檔部分分，只有 \(01\) 怎么做？
那就是區間答案就是 \(min\) 0,1 的個數。

可以從前到后掃描線，將 0 看做 \(-1\)，利用前綴和來計算。

用線段樹可以做到 \(O(nlogn)\)，但考慮每次前綴和的變化量為 1，可以開桶統計每種前綴和的個數，做到 \(O(n)\) 。

對于一般情況，枚舉分界 \(x\) ，將 \(\le x\) 的數看做 \(0\)，其余看做 \(1\)，然后將所有 \(x\) 的答案加起來，可以發現這樣是對的。

于是 \(a_i=2^k\) 就做完了，但對于一般情況，不能每次都 \(O(n)\) 計算。

發現非 \(0\) 數的總和是 \(nlogV\) 的，考慮如過以某個點為端點的區間中位數一定為零，那么可以直接計算，稱這些位置是無效的。

設非 \(0\) 的數有 \(m\) 個，那么有效位置不超過 \(3m\) 個。

考慮如何求出有效的位置，枚舉非零數，然后向左向右擴展，需要記錄前后綴的某個最值。

std 實現的比較隨意，時間復雜度沒有仔細分析，但不超過 \(O(nlog^2V)\)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,P=1e9+7,i2=P+1>>1;
int n,ans,c[N],d[N<<1];
vector<int>p[N];
bool vis[N],ban[N];
inline int md(int x){
	return x>=P?x-P:x;
}
int calc(vector<pair<int,int> >&a,int lim){
	int res=0;
	for(int i=0,j,s;j=i,i<a.size();i=j+1){
		c[s=1]=(a[i].second>=lim?1:-1);
		while(j+1<a.size()&&a[j+1].first==a[j].first+1)++j,c[++s]=(a[j].second>=lim?1:-1);
		int cl=0,s1=0,s2=0,c1=0,c2=1;
		d[n]=1;
		for(int k=1;k<=s;++k){
			c[k]+=c[k-1],cl=md(cl+k);
			if(c[k]<c[k-1]){
				s1=(1ll*(P-c[k])*d[c[k]+n]+s1)%P;
				c1-=d[c[k]+n];
				s2=(1ll*(c[k]+P)*d[c[k]+n]+s2)%P;
				c2+=d[c[k]+n];
			}else{
				s2=(1ll*(P-c[k-1])*d[c[k-1]+n]+s2)%P;
				c2-=d[c[k-1]+n];
				s1=(1ll*(c[k-1]+P)*d[c[k-1]+n]+s1)%P;
				c1+=d[c[k-1]+n];
			}
			res=(1ll*(P-c[k])*c1+s1+1ll*(c[k]+P)*c2+P-s2+res+cl)%P;
			s2=md(s2+md(c[k]+P)),++d[c[k]+n],++c2;
		}
		for(int i=0;i<=s;++i)d[c[i]+n]=0;
	}
	res=1ll*res*i2%P;
	return res;
}
int solve(vector<pair<int,int> >&a){
	sort(a.begin(),a.end());
	int sz=a.size(),mx=1;
	for(int i=0,o=1e9;i<sz;++i){
		o=min(o,2*i-a[i].first);
		vis[a[i].first]=true,mx=max(mx,a[i].second);
		for(int j=a[i].first+1,ed=(i==sz-1)?n:a[i+1].first-1;j<=ed;++j){
			if(2*i-j+1<o)break;
			vis[j]=true;
			a.push_back(make_pair(j,0));
		}
	}
	for(int i=sz-1,o=-1e9;~i;--i){
		o=max(o,2*i-a[i].first);
		for(int j=a[i].first-1,ed=i?a[i-1].first+1:1;j>=ed;--j){
			if(2*i-j-1>o||vis[j])break;
			vis[j]=true;
			a.push_back(make_pair(j,0));
		}
	}
	sort(a.begin(),a.end());
	int res=0;
	for(int i=1;i<=mx;++i)res=md(res+calc(a,i));
	for(int i=0,j;j=i,i<a.size();i=j+1){
		while(j+1<a.size()&&a[j+1].first==a[j].first+1)++j;
		for(int k=i,w;k<=j;++k)if(a[k].second){
			w=(1ll*(a[i].first-1)*(n-a[k].first+1)+1ll*(n-a[j].first)*a[k].first-1ll*(a[i].first-1)*(n-a[j].first))%P;
			res=(1ll*w*a[k].second+res)%P;
		}
	}
	for(auto v:a)vis[v.first]=false;
	return res;
}
int main(){
	freopen("unnamed.in","r",stdin);
	freopen("unnamed.out","w",stdout);
	scanf("%d",&n);
	for(int i=1,x;i<=n;++i){
		scanf("%d",&x);
		p[x].push_back(i);
	}
	for(int i=2;i<=1000000;++i)if(!ban[i]){
		long long x=i;
		vector<pair<int,int> >tmp;
		for(int j=i;j<=1000000;j+=i)ban[j]=true;
		for(int j=1;x<=1000000;x*=i,++j)
			for(int k=x;k<=1000000;k+=x)if((k/x)%i)
				for(auto v:p[k])tmp.push_back(make_pair(v,j));
		if(!tmp.empty())ans=md(ans+solve(tmp));
	}
	printf("%d\n",ans);
	return 0;
}