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 MaxN = 10000005;
int n, m;
bool snt[MaxN];
int ps[MaxN];
long long Count[MaxN];
vector<pair<long long, long long>> Quantum;
void init(int x) {
  for (int i = 0; i <= x; i++) {
    snt[i] = true;
    Count[i] = 0;
  }
  snt[0] = snt[1] = false;
  int t = sqrt(x) + 1;
  for (int i = 1; i <= t; i++) {
    if (snt[i] == true) {
      for (int j = i * i; j <= x; j += i) {
        snt[j] = false;
      }
    }
  }
  for (int i = 2; i <= x; i++) {
    for (int j = i; j <= x; j += i) {
      Count[i] += ps[j];
    }
  }
  m = 0;
  for (long long i = 1; i <= x; i++) {
    if (snt[i]) {
      m++;
      for (long long j = i * i; j <= x; j = j * i) {
        Count[i] += Count[j];
      }
    }
  }
  Quantum.resize(m);
  int j = 0;
  for (long long i = 2; i <= x; i++) {
    if (snt[i]) {
      Quantum[j] = make_pair(i, Count[i]);
      j++;
    }
  }
}
long long sl(long long Num, long long val) {
  long long Res = 0, t = val;
  while (t <= Num) {
    Res = Res + Num / t;
    t = t * val;
  }
  return Res;
}
bool Check(long long x) {
  for (int i = m - 1; i >= 0; i--) {
    if (sl(x, Quantum[i].first) < Quantum[i].second) {
      return false;
    }
  }
  return true;
}
long long BS(long long Left, long long Right) {
  while (Left <= Right) {
    long long Mid = (Left + Right) / 2;
    if (Check(Mid)) {
      Right = Mid - 1;
    } else {
      Left = Mid + 1;
    }
  }
  return Left;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  ps[0] = n;
  long long Max = 0, x;
  for (int i = 0; i < n; i++) {
    cin >> x;
    Max = max(Max, x);
    ps[x + 1]--;
  }
  for (int i = 1; i <= Max; i++) {
    ps[i] = ps[i - 1] + ps[i];
  }
  init(Max);
  cout << BS(1, (long long)1e14);
  return 0;
}