Codeforces485D(SummerTrainingDay01-K)

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 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.

Examples

input

3
3 4 5

output

2

 //2017-08-17

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int N = ;

 const int M = ;

 //book[i]记录i是否出现过，pre[i]表示比i小的出现过的最大的数

 int a[N], n, book[M], pre[M];

 int main()

 {

     while (scanf("%d", &n) != EOF)

     {

         memset(book, , sizeof(book));

         for (int i = ; i < n; i++){

             scanf("%d", &a[i]);

             book[a[i]] = ;

         }

         sort(a, a + n);

         n = unique(a, a+n)-a;

         int ans = , maxinum = (a[n-]<<), ptr = ;

         for(int i = ; i <= maxinum; i++){

             pre[i] = ptr;

             if(book[i])ptr = i;

         }

         for (int i = ; i < n; i++){

             for (int j = a[i]<<; j <= maxinum; j+=a[i]){

                 ans = max(ans, a[i]-j+pre[j]);

             }

         }

         printf("%d\n", ans);

     }

     return ;

 }