Problem: In a far away galaxy there is war again. The treacherous Republic made k precision strikes of power ai on the Empire possessions. To cope with the republican threat, the Supreme Council decided to deal a decisive blow to the enemy forces. 

To successfully complete the conflict, the confrontation balance after the blow should be a positive integer. The balance of confrontation is a number that looks like <image>, where p = n! (n is the power of the Imperial strike), <image>. After many years of war the Empire's resources are low. So to reduce the costs, n should be a minimum positive integer that is approved by the commanders.

Help the Empire, find the minimum positive integer n, where the described fraction is a positive integer.

Input

The first line contains integer k (1 ≤ k ≤ 106). The second line contains k integers a1, a2, ..., ak (1 ≤ ai ≤ 107).

Output

Print the minimum positive integer n, needed for the Empire to win.

Please, do not use the %lld to read or write 64-but integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples

Input

2
1000 1000


Output

2000

Input

1
2


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
const int ten[] = {1,      10,      100,      1000,      10000,
                   100000, 1000000, 10000000, 100000000, 1000000000};
const int fact[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
const int N = 1000000;
const int M = 10000000;
bool mark[M + 1];
long long cnt[N], d[M + 1], n, pn, a[N], p[N], factor[M + 1];
bool check(long long x) {
  for (int i = 0; i < pn; i++) {
    long long count = 0;
    for (long long k = p[i]; k <= x && k > 0; k *= p[i]) {
      count += x / k;
      if (count >= cnt[i]) break;
    }
    if (count < cnt[i]) return false;
  }
  return true;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  sort(a, a + n);
  pn = 0;
  memset(mark, 0, sizeof(mark));
  for (int i = 2; i <= M; i++) {
    if (!mark[i]) {
      factor[i] = pn;
      p[pn++] = i;
    }
    for (int j = 0; j < pn && i * p[j] <= M; j++) {
      mark[i * p[j]] = true;
      factor[i * p[j]] = j;
      if (i % p[j] == 0) break;
    }
  }
  for (int j = n - 1, i = M; i >= 2; i--) {
    while (j >= 0 && a[j] >= i) j--;
    d[i] = n - j - 1;
  }
  memset(cnt, 0, sizeof(cnt));
  for (int i = M; i >= 2; i--) {
    cnt[factor[i]] += d[i];
    d[i / p[factor[i]]] += d[i];
  }
  long long l = a[n - 1], r = a[n - 1] * 1ll * n, mid;
  while (l < r) {
    mid = (l + r) / 2;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  cout << l << endl;
  return 0;
}