#include <bits/stdc++.h>
const unsigned long long inf = 1LL << 61;
const double eps = 1e-5;
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
struct Node {
  int x, y;
};
struct cmp {
  bool operator()(Node a, Node b) {
    if (a.x == b.x) return a.y > b.y;
    return a.x > b.x;
  }
};
int ans, n;
int a[200010];
bool cmp(int a, int b) { return a > b; }
int main() {
  scanf("%d", &n);
  ans = 0;
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  sort(a, a + n);
  for (int i = 0; i < n - 1; ++i)
    if (i == 0 || a[i] != a[i - 1]) {
      int j = a[i] + a[i], p;
      while (j <= a[n - 1]) {
        p = lower_bound(a, a + n, j) - a;
        if (p > 0) ans = (ans < (a[p - 1] % a[i]) ? a[p - 1] % a[i] : ans);
        ;
        j += a[i];
      }
      ans = (ans < (a[n - 1] % a[i]) ? a[n - 1] % a[i] : ans);
      ;
    }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Please formulate 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>
const unsigned long long inf = 1LL << 61;
const double eps = 1e-5;
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
struct Node {
  int x, y;
};
struct cmp {
  bool operator()(Node a, Node b) {
    if (a.x == b.x) return a.y > b.y;
    return a.x > b.x;
  }
};
int ans, n;
int a[200010];
bool cmp(int a, int b) { return a > b; }
int main() {
  scanf("%d", &n);
  ans = 0;
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  sort(a, a + n);
  for (int i = 0; i < n - 1; ++i)
    if (i == 0 || a[i] != a[i - 1]) {
      int j = a[i] + a[i], p;
      while (j <= a[n - 1]) {
        p = lower_bound(a, a + n, j) - a;
        if (p > 0) ans = (ans < (a[p - 1] % a[i]) ? a[p - 1] % a[i] : ans);
        ;
        j += a[i];
      }
      ans = (ans < (a[n - 1] % a[i]) ? a[n - 1] % a[i] : ans);
      ;
    }
  printf("%d\n", ans);
  return 0;
}

```