#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000;
const int mod = 1000000007;
const int N = 200005;
int n;
int a[N];
int solve(int cur) {
  int tmp = cur;
  int mx = 0;
  while (tmp <= a[n - 1]) {
    tmp += cur;
    int ind = lower_bound(a, a + n, tmp) - a;
    --ind;
    if (ind >= 0) {
      if (a[ind] > cur) {
        mx = max(mx, a[ind] % cur);
      }
    }
  }
  return mx;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  sort(a, a + n);
  int cur = 1;
  for (int i = 1; i < n; ++i) {
    if (a[cur - 1] != a[i]) a[cur++] = a[i];
  }
  n = cur;
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    int dp = solve(a[i]);
    ans = max(dp, ans);
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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 inf = 1000000000;
const int mod = 1000000007;
const int N = 200005;
int n;
int a[N];
int solve(int cur) {
  int tmp = cur;
  int mx = 0;
  while (tmp <= a[n - 1]) {
    tmp += cur;
    int ind = lower_bound(a, a + n, tmp) - a;
    --ind;
    if (ind >= 0) {
      if (a[ind] > cur) {
        mx = max(mx, a[ind] % cur);
      }
    }
  }
  return mx;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  sort(a, a + n);
  int cur = 1;
  for (int i = 1; i < n; ++i) {
    if (a[cur - 1] != a[i]) a[cur++] = a[i];
  }
  n = cur;
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    int dp = solve(a[i]);
    ans = max(dp, ans);
  }
  cout << ans << endl;
  return 0;
}

```