二分寻找对于指定pos的最左因数点和最右因数点。
/* 5288 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int mod = 1e9+;
const int maxn = 1e5+;
const int maxm = ;
vi vc[maxm];
vi fac[maxm];
int a[maxn]; void init() {
int i, j, k; for (i=; i<maxm; ++i) {
for (j=; j*j<=i; ++j) {
if (i%j == ) {
fac[i].pb(j);
k = i / j;
if (k != j)
fac[i].pb(k);
}
}
}
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int n;
int l, r, tmp;
vi::iterator iter;
__int64 ans; init();
while (scanf("%d", &n) != EOF) {
rep(i, , n+) {
scanf("%d", &a[i]);
vc[a[i]].pb(i);
} int sz;
ans = ; rep(i, , n+) {
l = ;
r = n+;
sz = SZ(fac[a[i]]);
rep(j, , sz) {
tmp = fac[a[i]][j];
iter = upper_bound(all(vc[tmp]), i);
if (iter != vc[tmp].end()) {
r = min(r, *iter);
}
if (iter!=vc[tmp].begin()) {
--iter;
if (*iter != i)
l = max(l, *iter);
else if (iter != vc[tmp].begin()) {
--iter;
l = max(l, *iter);
}
}
}
#ifndef ONLINE_JUDGE
tmp = (r-i) * (i-l);
// printf("%d: l = %d, r = %d, c = %d\n", i, l, r, tmp);
#endif
ans = (ans + 1LL * (r-i) * (i-l) % mod) % mod;
} printf("%I64d\n", ans); rep(i, , maxm)
vc[i].clear();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}