#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int M = 1000010;
int n;
int a[N];
int vis[M];
int num[M];
int main() {
  while (scanf("%d", &n) != EOF) {
    int mx = 0, ans = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &a[i]);
      vis[a[i]] = 1;
      mx = max(mx, a[i]);
    }
    for (int i = 1; i <= mx; ++i) {
      if (vis[i])
        num[i] = i;
      else
        num[i] = num[i - 1];
    }
    for (int i = 1; i <= mx; ++i) {
      if (!vis[i]) continue;
      if (mx % i > ans) ans = mx % i;
      for (int j = i * 2; j <= mx; j += i) {
        if (ans < num[j - 1] % i) ans = num[j - 1] % i;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

You are given a sequence a consisting of n integers. Find the maximum possible value of <image> (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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int M = 1000010;
int n;
int a[N];
int vis[M];
int num[M];
int main() {
  while (scanf("%d", &n) != EOF) {
    int mx = 0, ans = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &a[i]);
      vis[a[i]] = 1;
      mx = max(mx, a[i]);
    }
    for (int i = 1; i <= mx; ++i) {
      if (vis[i])
        num[i] = i;
      else
        num[i] = num[i - 1];
    }
    for (int i = 1; i <= mx; ++i) {
      if (!vis[i]) continue;
      if (mx % i > ans) ans = mx % i;
      for (int j = i * 2; j <= mx; j += i) {
        if (ans < num[j - 1] % i) ans = num[j - 1] % i;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

```