一开始把图想错了，想了 40 分钟。后来图画对了，但还是没想出来。

正解的思想值得借鉴学习，不会挺正常的。

对于稠密图的分析，可以先从特殊点、特殊边、特殊限制入手，从而掌握一类与这种点有关的性质。

题意：给出一张有向图 ，每个点有点权 ， 中有边 当且仅当 ，求 权值和最大的反链的权值和。

。

这张图看着十分鬼畜，边非常多。

正解是从 这个特殊数入手。

我们发现所有的偶数都能够互相到达，即最多选一个偶数。

接下来考虑那些奇数怎么选。

那么我们就要研究 奇偶性确定的时候， 如何到达 。

假设 是奇数， 是偶数。

那么 可以先尝试一步变成偶数，然后直达 。

设 为 的最小质因子，那么 显然是 能往前走到的最小的数，同时它显然是一个偶数！

那么我们就可以得到此时 能到达 的充要条件：。

类似的，如果 都是奇数，那 可达 当且仅当 。

如果 为偶数， 为奇数，则条件为 。

有了以上性质，就可以解决原问题了。

假如我们选一个偶数 ，那么剩下的奇数 要满足下列两个条件中的一个：

1. 且
2. 且

对于每个 ，我们都能用树状数组维护出满足条件的 之和。

考虑全是奇数的情况，此时需要 ，可以枚举中间的一个分界点统计答案。

#include <bits/stdc++.h>
using namespace std;

namespace FastIO {
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a)
	{
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n')
	{
		int c[35],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL 
	#undef gc 
	#undef flush
}
using namespace FastIO;
const int N = 1e6 + 5;
typedef long long ll;
int n,a[N],p[N];

struct BIT{
	ll tr[N << 1];
	#define lowbit(x) (x&(-x))
	inline void upd(int x,int v) { for(int i = x;i <= n + n;i += lowbit(i)) tr[i] += v;}
	inline ll Sum(int x) { ll res = 0;for(int i = x;i;i ^= lowbit(i)) res += tr[i];return res;}
};
BIT T1,T2;
ll dif[N << 1];

int main()
{
	read(n);
	for(int i = 1;i <= n;i++) read(a[i]);
	for(int i = 2;i <= n;i++)
	{
		if(p[i]) continue;
		for(int j = i;j <= n;j += i)
			if(!p[j]) p[j] = i;
	}
	for(int i = 3;i <= n;i += 2)
		T1.upd(i - p[i] + 1,a[i]);
	ll ans = 0;
	for(int i = 2;i <= n;i++)
		if(i & 1) T1.upd(i - p[i] + 1,-a[i]),T2.upd(i + p[i],a[i]);
		else ans = max(ans,a[i] + T2.Sum(n + n) - T2.Sum(i) + T1.Sum(i));
	for(int i = 3;i <= n;i += 2) dif[i - p[i] + 1] += a[i],dif[i + p[i]] -= a[i];
	for(int i = 1;i <= n + n;i++) dif[i] += dif[i - 1],ans = max(ans,dif[i]);
	write(ans + a[1]);
	return 0;
}