*2800 的 DS，不过还是被我自己想出来了
u1s1 这个 D1C 比某些 D1D 不知道难到什么地方去了
首先碰到这类问题我们肯定考虑枚举什么东西，然后在枚举过程中用个什么东西维护答案，求出其对答案的贡献。此题一个很直观的想法是枚举左端点，但很遗憾此题涉及 gcd，不太好直接维护。故我们换个想法，枚举答案。
我们先预处理出每个数的所有因子——这个显然可以在 \(n\ln n\) 的时间内求出。然后从大到小动态地枚举一个指针 \(i\)。容易注意到的一件事情是如果 \(f(l,r)\geq i\)，那么 \(f(l,r-1)\geq i\)。故考虑设 \(t_l\) 为以 \(l\) 为左端点的区间中，最小的满足 \(f(l,r)<i\) 的 \(r\)。那么显然满足 \(f(l,r)\geq i\) 的区间 \([l,r]\) 的个数为 \(\sum\limits_{i=1}^n(t_i-i)=\sum\limits_{i=1}^nt_i-\dfrac{n(n-1)}{2}\)，而答案又显然可以用差分的思想转化为对于所有 \(i\)，满足 \(f(l,r)\geq i\) 的区间 \([l,r]\) 的个数之和。
考虑当指针 \(i\) 从 \(i+1\) 变为 \(i\) 的时候会对 \(t_l\) 造成什么影响。显然只有满足 \(a_j\) 为 \(i\) 的倍数的位置 \(j\) 才有可能对 \(t_l\) 造成影响，故考虑将满足 \(a_j\) 是 \(i\) 的倍数的位置 \(j\) 按照下标从小到大排好，假设为 \(p_1,p_2,\dots,p_k\)，那么有：
- 若 \(k=1\)，一个数显然不会对 \(t_l\) 产生任何影响，故不考虑 \(k=1\) 的情况。
- 若 \(k>2\)，那么：
- 对于 \(l\in [1,x_1]\)，\(\forall r\in[l,x_{m-1}-1]\)，区间 \([l,r]\) 之外都有两个 \(i\) 的倍数（\(a_{x_{m-1}},a_{x_m}\)），故 \(t_l\leftarrow\max(t_l,x_{m-1})\)
- 对于 \(l\in [x_1+1,x_2]\)，\(\forall r\in[l,x_{m}-1]\)，区间 \([l,r]\) 之外都有两个 \(i\) 的倍数（\(a_1,a_{x_m}\)），故 \(t_l\leftarrow\max(t_l,x_{m})\)
- 对于 \(l\in [x_2+1,n]\)，\(\forall r\in[l,n]\)，区间 \([l,r]\) 之外都有两个 \(i\) 的倍数（\(a_1,a_2\)），故 \(t_l\leftarrow\max(t_l,n+1)\)
于是现在我们要实现支持区间取 \(\max\)，全局求和的数据结构，这个显然是数据结构不太好直接维护的，第一篇题解说要这东西要用到什么吉司机线段树（反正我不会就对了）。不过我们静下心来好好想想，真的要这么麻烦吗？这个 \(t\) 数组就没有什么性质吗？不难发现，如果 \(f(l,r)\geq i\)，那么 \(f(l+1,r)\geq i\)。故我们有 \(t_l\leq t_{l+1}\)。也就是说对于一次将 \(t_l,t_{l+1},t_{l+2},\dots,t_r\) 与 \(x\) 取 \(\max\) 的操作，我们显然可以找到一个断点 \(k\) 使得 \(t_l,t_{l+1},\dots,t_k\) 均小于 \(x\)，\(t_{k+1},t_{k+2},\dots,t_r\) 均 \(\ge x\)，故我们只需对 \([l,k]\) 进行区间赋值操作，这显然是普通线段树可以维护的。这个 \(k\) 可以通过线段树二分求出，二分出第一个 \(\geq x\) 的位置 \(p\) 并与 \(r+1\) 取 \(\min\)，然后将区间 \([l,p-1]\) 赋上 \(x\) 即可。
时间复杂度 \(nd(a_i)+n\log n\)。
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
#define FILE_SIZE 1<<23
char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
inline void putc(char x){(*p3++=x);}
template<typename T> void read(T &x){
x=0;char c=getchar();T neg=0;
while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(neg) x=(~x)+1;
}
template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=2e5;
const int MAX_ITEM=3e6;
int n,a[MAXN+5];vector<int> pos[MAXN+5];
struct chain_list{
int hd[MAXN+5],v[MAX_ITEM+5],nxt[MAX_ITEM+5],item_n=0;
void ins(int p,int q){v[++item_n]=q;nxt[item_n]=hd[p];hd[p]=item_n;}
} fac;
void prework(int n){
for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i) fac.ins(j,i);
}
struct node{int l,r,tag,mx;ll sum;} s[MAXN*4+5];
void pushup(int k){
s[k].sum=s[k<<1].sum+s[k<<1|1].sum;
s[k].mx=max(s[k<<1].mx,s[k<<1|1].mx);
}
void pushdown(int k){
if(s[k].tag!=0){
s[k<<1].mx=s[k].tag;s[k<<1].tag=s[k].tag;
s[k<<1].sum=1ll*(s[k<<1].r-s[k<<1].l+1)*s[k].tag;
s[k<<1|1].mx=s[k].tag;s[k<<1|1].tag=s[k].tag;
s[k<<1|1].sum=1ll*(s[k<<1|1].r-s[k<<1|1].l+1)*s[k].tag;
s[k].tag=0;
}
}
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;if(l==r){s[k].sum=l;s[k].mx=l;return;}
int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
pushup(k);
}
void modify(int k,int l,int r,int x){
if(l<=s[k].l&&s[k].r<=r){
s[k].tag=x;s[k].mx=x;
s[k].sum=1ll*(s[k].r-s[k].l+1)*x;return;
} pushdown(k);int mid=s[k].l+s[k].r>>1;
if(r<=mid) modify(k<<1,l,r,x);
else if(l>mid) modify(k<<1|1,l,r,x);
else modify(k<<1,l,mid,x),modify(k<<1|1,mid+1,r,x);
pushup(k);
}
int get_first_le(int k,int x){//find the first element >= x
if(s[k].l==s[k].r) return s[k].l;
pushdown(k);
if(s[k<<1|1].mx<x) return s[k].r+1;
else if(s[k<<1].mx<x) return get_first_le(k<<1|1,x);
else return get_first_le(k<<1,x);
}
void deal_max(int l,int r,int x){
if(l>r) return;
int pos=get_first_le(1,x)-1;
// printf("%d %d %d %d\n",l,r,x,pos);
if(pos>r) pos=r;if(pos<l) return;
modify(1,l,pos,x);
}
int main(){
scanf("%d",&n);prework(MAXN);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) for(int e=fac.hd[a[i]];e;e=fac.nxt[e])
pos[fac.v[e]].pb(i);
build(1,1,n);ll ans=0;
for(int i=MAXN;i;i--){
if(pos[i].size()>=2){
int fst=pos[i][0],fst_se=pos[i][1];
int lst=pos[i][pos[i].size()-1],lst_se=pos[i][pos[i].size()-2];
deal_max(1,fst,lst_se);
deal_max(fst+1,fst_se,lst);
deal_max(fst_se+1,n,n+1);
} ans+=s[1].sum-1ll*n*(n+1)/2;
// printf("%d %lld\n",i,s[1].sum);
} printf("%lld\n",ans);
return 0;
}