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 a_i divided by a_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·10⁵).

The second line contains n space-separated integers a_i (1 ≤ a_i ≤ 10⁶).

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
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define N 2*100000+10const int maxn=1000000+10;typedef long long ll;using namespace std;int a[N];int n;int C(int x){ int w=x,ans=0; while (w
               
                =0;i--){ if (i
                
                 =a[i]-1) break; ans=max(ans,C(a[i])); } printf("%d\n",ans); return 0;}