摘要：
给出个数组，选择不同的三个下标，最大化。其中，前者只需要算。后者可以求出之后，排序，双指针计算。于是就做到了的复杂度。考虑优化这个暴力：先算。然后从后往前枚举，如果则以为模数计算上面后面的第二类。显然要考虑的是一段后缀。下面证明只有个：假如最终的满足。根据第一类，有：。令，，且至少是类似斐波拉契数列增长的，而且，于是长度为级别。
给出个数组(a)，选择不同的三个下标(i,j,k)，最大化((a_i+a_j)mod a_k)。
(nle 2*10^5)
对(a_i)排序。
先讲暴力：枚举模数(a_k)，令(b_i=a_i mod a_k)。分成两类：(b_i+b_jge a_k)和(b_i+b_j<a_k)。其中，前者只需要算((a_{k-1}+a_{k-2})mod a_k)。证明：假如存在(p>k)，且(a_{p} mod a_k>a_{k-2})，则有(a_{k-2}+a_k<a_p)，此时选择((a_{k-2}+a_k)mod a_p)更优。后者可以求出(b_i)之后，排序，双指针计算。于是就做到了(O(n^2lg n))的复杂度。
考虑优化这个暴力：先算(ans=max ((a_{k-2}+a_{k-1})mod a_k))。然后(k)从后往前枚举，如果(a_k-1>ans)则以(a_k)为模数计算上面后面的第二类。
显然要考虑的(k)是一段后缀。下面证明只有(O(log V))个：
假如最终的(ans)满足(ans<a_sle a_{s+1}le dots le a_n)。
根据第一类，有：(forall iin[s,n-2],ansge (a_i+a_{i+1})mod a_{i+2}ge a_i+a_{i+1}-a_{i+2})。于是有(a_{i+2}-ansge (a_{i}-ans)+(a_{i+1}-ans))。令(c_i=a_i-ans)，(c_i>0)，且(c_i)至少是类似斐波拉契数列增长的，而且(c_n=a_n-ans=O(V))，于是长度为(O(log V))级别。
总时间(O(nlog nlog V))。
using namespace std;
#include <bits/stdc++.h>
#define N 200005
int n;
int a[N],b[N];
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int ans=0;
for (int i=3;i<=n;++i)
ans=max(ans,(a[i-2]+a[i-1])%a[i]);
for (int j=n;j>=1;--j)
if (a[j]-1>ans){
int k=0;
for (int i=1;i<j;++i) b[++k]=a[i];
for (int i=j+1;i<=n;++i) b[++k]=a[i]%a[j];
sort(b+1,b+k+1);
// ans=max(ans,(b[k]+b[k-1])%a[j]);
for (int i=k,p=1;i>=1;--i){
p=min(p,i-1);
while (p<=i-1 && b[p]+b[i]<a[j])
++p;
if (p>1)
ans=max(ans,(b[p-1]+b[i])%a[j]);
}
}
printf("%d
",ans);
return 0;
}