#include <bits/stdc++.h>
using namespace std;
bool check(long long n, long long pos) { return n & (1 << pos); }
long long Set(long long n, long long pos) { return n = n | (1 << pos); }
long long arr[300005];
long long up[2000006];
int main() {
  long long i, j, k, l, m, n, o, r, q;
  long long testcase;
  long long input, flag, tag, ans;
  scanf("%lld", &n);
  m = -1;
  for (i = 1; i <= n; i++) {
    scanf("%lld", &arr[i]);
    m = max(m, arr[i]);
  }
  m *= 2;
  sort(arr + 1, arr + 1 + n);
  n = unique(arr + 1, arr + 1 + n) - (arr + 1);
  if (n == 1) {
    cout << 0 << endl;
    return 0;
  }
  for (i = 1; i <= n; i++) {
    up[arr[i] + 1] = arr[i];
  }
  for (i = 1; i <= m; i++) {
    if (up[i] == 0) {
      up[i] = up[i - 1];
    }
  }
  ans = 0;
  for (i = 1; i < n; i++) {
    for (j = arr[i] * 2; j <= m; j += i) {
      flag = up[j];
      ans = max(ans, flag % arr[i]);
    }
  }
  printf("%lld\n", ans);
}

### Prompt

Create a solution in cpp for 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;
bool check(long long n, long long pos) { return n & (1 << pos); }
long long Set(long long n, long long pos) { return n = n | (1 << pos); }
long long arr[300005];
long long up[2000006];
int main() {
  long long i, j, k, l, m, n, o, r, q;
  long long testcase;
  long long input, flag, tag, ans;
  scanf("%lld", &n);
  m = -1;
  for (i = 1; i <= n; i++) {
    scanf("%lld", &arr[i]);
    m = max(m, arr[i]);
  }
  m *= 2;
  sort(arr + 1, arr + 1 + n);
  n = unique(arr + 1, arr + 1 + n) - (arr + 1);
  if (n == 1) {
    cout << 0 << endl;
    return 0;
  }
  for (i = 1; i <= n; i++) {
    up[arr[i] + 1] = arr[i];
  }
  for (i = 1; i <= m; i++) {
    if (up[i] == 0) {
      up[i] = up[i - 1];
    }
  }
  ans = 0;
  for (i = 1; i < n; i++) {
    for (j = arr[i] * 2; j <= m; j += i) {
      flag = up[j];
      ans = max(ans, flag % arr[i]);
    }
  }
  printf("%lld\n", ans);
}

```