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 JAVA):

Solution:
import static java.lang.Math.max;

import java.io.*;

public class E {

    static void solve() throws IOException {
        int k = nextInt();
        int[] a = new int[k];
        for (int i = 0; i < k; i++) {
            a[i] = nextInt();
        }
        int maxValue = 0;
        for (int value : a) {
            maxValue = max(maxValue, value);
        }
        int[] primes = calcP(maxValue + 1);

        int[] count = new int[maxValue + 1];
        for (int value : a) {
            ++count[value];
        }
        for (int i = maxValue; i > 0; --i) {
            count[i - 1] += count[i];
        }

        long[] degInFact = new long[primes.length];

        for (int primeIndex = 0; primeIndex < primes.length; ++primeIndex) {
            int prime = primes[primeIndex];
            while (true) {
                for (int i = prime; i <= maxValue; i += prime) {
                    degInFact[primeIndex] += count[i];
                }
                long next = (long) prime * primes[primeIndex];
                if (next > maxValue) {
                    break;
                }
                prime = (int) next;
            }
        }

        long minN = 0;
        for (int primeIndex = 0; primeIndex < primes.length; primeIndex++) {
            long val = degInFact[primeIndex] * (primes[primeIndex] - 1);
            if (minN < val) {
                minN = val;
            }
        }
        long sum = sum(a);
        long maxN = minN + 1;

        for (int primeIndex = primes.length - 1; primeIndex >= 0; --primeIndex) {
            if (!largeEnough(maxN, primes[primeIndex], degInFact[primeIndex])) {
                maxN = sum;
                while (maxN > minN + 1) {
                    long midN = maxN + minN >>> 1;
                    if (largeEnough(midN, primes[primeIndex],
                            degInFact[primeIndex])) {
                        maxN = midN;
                    } else {
                        minN = midN;
                    }
                }
            }
        }
        System.out.println(maxN);
    }

    private static boolean largeEnough(long checkN, int prime, long pow) {
        long val = checkN;
        for (val /= prime; val > 0; val /= prime) {
            pow -= val;
            if (pow <= 0) {
                return true;
            }
        }
        return false;
    }

    private static long sum(int[] a) {
        long s = 0;
        for (int value : a) {
            s += value;
        }
        return s;
    }

    static int[] calcP(int max) {
        if (max <= 2) {
            return new int[0];
        }
        boolean[] notPrime = new boolean[max >>> 1];
        notPrime[0] = true;
        for (int val = 1; val * val < max; val += 2) {
            if (!notPrime[val >>> 1]) {
                for (int j = val * val; j < max; j += 2 * val) {
                    notPrime[j >>> 1] = true;
                }
            }
        }
        int cnt = 1;
        for (int i = 0; i < notPrime.length; i++) {
            if (!notPrime[i])
                cnt++;
        }
        int[] p = new int[cnt];
        cnt = 0;
        p[cnt++] = 2;
        for (int i = 0; i < notPrime.length; i++) {
            if (!notPrime[i])
                p[cnt++] = 2 * i + 1;
        }
        return p;
    }

    static BufferedReader br;

    public static void main(String[] args) throws IOException {
        InputStream input = System.in;
        File file = new File("e.in");
        if (file.exists() && file.canRead()) {
            input = new FileInputStream(file);
        }
        br = new BufferedReader(new InputStreamReader(input));
        solve();
    }

    static int nextInt() throws IOException {
        int c = br.read();
        while (c < '0' || c > '9') {
            c = br.read();
        }
        int ret = 0;
        while (c >= '0' && c <= '9') {
            ret = ret * 10 + c - '0';
            c = br.read();
        }
        return ret;
    }
}