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 MAX = 1e7;
vector<int> bpf(MAX + 1, 1);
vector<int> prime;
bool valid(long long num, vector<long long>& pow) {
  for (typeof(prime.begin()) it = prime.begin(); it != prime.end(); ++it) {
    long long npow = 0;
    for (long long p = *it; p <= num; p *= *it) {
      npow += num / p;
    }
    if (npow < pow[*it]) return false;
  }
  return true;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  for (int i = 2; i <= MAX;) {
    for (int j = i; j <= MAX; j += i) bpf[j] = i;
    while (++i <= MAX && bpf[i] > 1)
      ;
  }
  for (int i = 2; i <= MAX; ++i) {
    if (bpf[i] == i) prime.push_back(i);
  }
  int n;
  cin >> n;
  deque<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  long long sum = accumulate(a.begin(), a.end(), 0ll);
  vector<long long> pow(MAX + 1);
  for (int i = 1; n > 0; ++i) {
    int tmp = i;
    while (tmp > 1) {
      pow[bpf[tmp]] += n;
      tmp /= bpf[tmp];
    }
    while (a.front() == i) {
      a.pop_front();
      --n;
    }
  }
  long long stp = 1;
  while (stp < sum) stp *= 2;
  long long num;
  for (num = 0; stp > 0; stp /= 2) {
    num += stp;
    if (valid(num, pow)) {
      num -= stp;
    }
  }
  cout << ++num;
  return 0;
}