#include <bits/stdc++.h>
using namespace std;
int ar[1000000 + 5], P[1000000 + 5][20], L[1000000 + 5];
void preProcess(int n) {
  int i, j;
  L[1] = 31 - __builtin_clz(1);
  for (i = 2; i <= n; i++) {
    P[i][0] = i;
    L[i] = 31 - __builtin_clz(i);
  }
  for (j = 1; (1 << j) <= n; j++) {
    for (i = 2; i + (1 << j) - 1 <= n; i++) {
      if (ar[P[i][j - 1]] >= ar[P[i + (1 << (j - 1))][j - 1]])
        P[i][j] = P[i][j - 1];
      else
        P[i][j] = P[i + (1 << (j - 1))][j - 1];
    }
  }
}
int query(int i, int j) {
  int k = L[j - i + 1];
  return max(ar[P[i][k]], ar[P[j - (1 << k) + 1][k]]);
}
int main() {
  int n, a, i, mx = 0, j;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &a);
    ar[a] = a;
    mx = max(mx, a);
  }
  preProcess(mx);
  int ans = 0;
  for (i = 2; i <= mx; i++) {
    if (ar[i] == 0) continue;
    for (j = i; j <= mx; j += i) {
      if (j + 1 > mx) continue;
      int tmp = query(j + 1, min(mx, j + i - 1));
      if (tmp != 0) ans = max(ans, tmp - j);
    }
  }
  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;
int ar[1000000 + 5], P[1000000 + 5][20], L[1000000 + 5];
void preProcess(int n) {
  int i, j;
  L[1] = 31 - __builtin_clz(1);
  for (i = 2; i <= n; i++) {
    P[i][0] = i;
    L[i] = 31 - __builtin_clz(i);
  }
  for (j = 1; (1 << j) <= n; j++) {
    for (i = 2; i + (1 << j) - 1 <= n; i++) {
      if (ar[P[i][j - 1]] >= ar[P[i + (1 << (j - 1))][j - 1]])
        P[i][j] = P[i][j - 1];
      else
        P[i][j] = P[i + (1 << (j - 1))][j - 1];
    }
  }
}
int query(int i, int j) {
  int k = L[j - i + 1];
  return max(ar[P[i][k]], ar[P[j - (1 << k) + 1][k]]);
}
int main() {
  int n, a, i, mx = 0, j;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &a);
    ar[a] = a;
    mx = max(mx, a);
  }
  preProcess(mx);
  int ans = 0;
  for (i = 2; i <= mx; i++) {
    if (ar[i] == 0) continue;
    for (j = i; j <= mx; j += i) {
      if (j + 1 > mx) continue;
      int tmp = query(j + 1, min(mx, j + i - 1));
      if (tmp != 0) ans = max(ans, tmp - j);
    }
  }
  printf("%d\n", ans);
  return 0;
}

```