Maximum Value
Time limit 1000 ms
Memory limit 262144 kB
You are given a sequence a consisting of n integers. Find the maximum possible value of (integer remainder of ai divided by aj), where 1 ≤ i, j ≤ n and ai ≥ aj.
Input
The first line contains integer n — the length of the sequence (1 ≤ n ≤ 2·105).
The second line contains n space-separated integers ai (1 ≤ ai ≤ 106).
Output
Print the answer to the problem.
Example
Input
3
3 4 5
Output
2 题意：求aj%ai的最大值，其中j>i;
分析：每次寻找小于k*aj的最大值，类似于素数筛，例如n=5时，3 4 5 6 7 ，我们如果查找对3取模的最大值，毫无疑问就是找到3到2*3中间的最大值； AC代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 2*100000+10
const int maxn=+;
typedef long long ll;
using namespace std;
int a[N];
int n;
int C(int x){
int w=x,ans=;
while (w<a[n-]){
w+=x;
int k=lower_bound(a,a+n,w)-a;
if (k==) continue;
else k--;
if (a[k]<=x) continue;
ans=max(ans,a[k]%x);
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
int ans=;
scanf("%d",&n);
for (int i=;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
for (int i=n-;i>=;i--){
if (i<n-&&a[i]==a[i+])
continue;
if (ans>=a[i]-)
break;
ans=max(ans,C(a[i]));
}
printf("%d\n",ans);
return ;
}