#include <bits/stdc++.h>
using namespace std;
long long int modpow(long long int a, long long int n, long long int temp) {
  long long int res = 1, y = a;
  while (n > 0) {
    if (n & 1) res = (res * y) % temp;
    y = (y * y) % temp;
    n /= 2;
  }
  return res % temp;
}
int arr[1000006];
int lowerit(int val, int n) {
  int low = 0, high = n - 1, mid;
  while (low <= high) {
    mid = (low + high) / 2;
    if (arr[mid] < val && (mid == n - 1 || arr[mid + 1] >= val))
      return arr[mid];
    else if (val > arr[mid])
      low = mid + 1;
    else
      high = mid - 1;
  }
  return -1;
}
int main() {
  int n, maxit = -(int)(1e9 + 7), ans = 0, i, val, val1, findit;
  scanf("%d", &n);
  for (i = 0; i < n; ++i) {
    scanf("%d", &arr[i]);
    maxit = ((maxit) > (arr[i]) ? (maxit) : (arr[i]));
  }
  sort(arr, arr + n);
  for (i = 0; i < n; ++i) {
    val = arr[i];
    if (i != 0 && val == arr[i - 1]) continue;
    val1 = 2 * val;
    while (1) {
      findit = lowerit(val1, n);
      if (findit < val) {
        if (val1 >= maxit) break;
        val1 += val;
        continue;
      }
      findit %= val;
      ans = ((ans) > (findit) ? (ans) : (findit));
      if (val1 >= maxit) break;
      val1 += val;
    }
  }
  printf("%d\n", ans);
  return 0;
}

### 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;
long long int modpow(long long int a, long long int n, long long int temp) {
  long long int res = 1, y = a;
  while (n > 0) {
    if (n & 1) res = (res * y) % temp;
    y = (y * y) % temp;
    n /= 2;
  }
  return res % temp;
}
int arr[1000006];
int lowerit(int val, int n) {
  int low = 0, high = n - 1, mid;
  while (low <= high) {
    mid = (low + high) / 2;
    if (arr[mid] < val && (mid == n - 1 || arr[mid + 1] >= val))
      return arr[mid];
    else if (val > arr[mid])
      low = mid + 1;
    else
      high = mid - 1;
  }
  return -1;
}
int main() {
  int n, maxit = -(int)(1e9 + 7), ans = 0, i, val, val1, findit;
  scanf("%d", &n);
  for (i = 0; i < n; ++i) {
    scanf("%d", &arr[i]);
    maxit = ((maxit) > (arr[i]) ? (maxit) : (arr[i]));
  }
  sort(arr, arr + n);
  for (i = 0; i < n; ++i) {
    val = arr[i];
    if (i != 0 && val == arr[i - 1]) continue;
    val1 = 2 * val;
    while (1) {
      findit = lowerit(val1, n);
      if (findit < val) {
        if (val1 >= maxit) break;
        val1 += val;
        continue;
      }
      findit %= val;
      ans = ((ans) > (findit) ? (ans) : (findit));
      if (val1 >= maxit) break;
      val1 += val;
    }
  }
  printf("%d\n", ans);
  return 0;
}

```