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>
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline void sub(long long &a, long long b) {
  a -= b;
  if (a < 0) a += 998244353;
}
inline void add(long long &a, long long b) {
  a += b;
  if (a >= 998244353) a -= 998244353;
}
inline long long mul(long long a, long long b, long long c) {
  return (a * b - (long long)((long double)a * b / c) * c + c) % c;
}
inline long long qp(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % 998244353;
    a = a * a % 998244353, b >>= 1;
  }
  return ans;
}
inline long long qp(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = mul(ans, a, c);
    a = mul(a, a, c), b >>= 1;
  }
  return ans;
}
using namespace std;
const long double pi = acos(-1);
const unsigned long long ba = 233;
const double eps = 1e-8;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int N = 10000000 + 10, maxn = 1000000 + 10, inf = 0x3f3f3f3f;
int prime[N], cnt, mi[N];
bool mark[N];
void init() {
  for (int i = 2; i < N; i++) {
    if (!mark[i]) prime[++cnt] = i, mi[i] = i;
    for (int j = 1; j <= cnt && i * prime[j] < N; j++) {
      mark[i * prime[j]] = 1;
      mi[i * prime[j]] = prime[j];
      if (i % prime[j] == 0) break;
    }
  }
}
long long a[N];
int main() {
  init();
  int n;
  scanf("%d", &n);
  long long l = 0, r = 0;
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    a[x]++;
    r += x;
  }
  for (int i = N - 2; i >= 1; i--) a[i] += a[i + 1];
  for (int i = N - 2; i >= 1; i--)
    if (mark[i]) {
      a[mi[i]] += a[i];
      a[i / mi[i]] += a[i];
    }
  auto ok = [&](long long x) {
    for (int i = 1; i <= cnt; i++) {
      long long sum = 0, te = x;
      while (te) sum += te / prime[i], te /= prime[i];
      if (sum < a[prime[i]]) return 0;
    }
    return 1;
  };
  while (l < r - 1) {
    long long m = (l + r) >> 1;
    if (ok(m))
      r = m;
    else
      l = m;
  }
  printf("%lld\n", r);
  return 0;
}