codeforces D. Maximum Value-蒲公英云

codeforces D. Maximum Value

D. Maximum Value

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a sequence a consisting of n integers. Find the maximum possible value of (integer remainder of a**i divided bya**j), where 1 ≤ i, j ≤ n and a**i ≥ a**j.

Input

The first line contains integer n — the length of the sequence (1 ≤ n ≤ 2·105).

The second line contains n space-separated integers a**i (1 ≤ a**i ≤ 106).

Output

Print the answer to the problem.

Examples

input

3
3 4 5

output

题意: 给你n个数, 求最大的ai%aj的值.

分析: 可以将原先数组排个序, 然后去重, 用类似于埃氏筛选的方法对于每个数a[i]枚举它的倍数, 然后对于每个倍数x, 找小于x的最大的a[k]; 那么a[i]-(x-a[k])就是a[k]模a[i]的值, (x-a[k])是最小的, 因此a[i]-(x-a[k])就是最大的, 不断更新答案就行啦.

开始是用二分找小于x的最大的值, 后来发现可以用一个数组来做;

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=2000010,MOD=1e9+7;
int a[200020];
int pre[N];
bool have[N];
int main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++) scanf("%d",a+i),have[a[i]]=1;
    sort(a,a+n);
    n = unique(a,a+n)-a;
    int mx = a[n-1];
    mx<<=1;
    int last=0;
    for(int i=1;i<=mx;i++){
        if(!have[i]) pre[i] = last;
        else{
            pre[i]=last;
            last=i;
        }
    }
    int ans=0;
    int i=a[0]==1;
    for(;i<n;i++){
        for(int j=a[i]+a[i];j<mx;j+=a[i]){
            if(j-a[n-1]>=a[i]) break;
            int ret = pre[j];
            if(j-ret >= a[i]) continue;
            ans = max(ans,a[i]-(j-ret));
        }
    }
    cout<<ans<<endl;
    return 0;
}