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 java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;

public class E {
    public static void increment(long[] A, int i, int j, int c) {
        A[i] += c;
        if (j < A.length)
            A[j] -= c;
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        int max = (int) 1e7 + 10;
        int n = in.readInt();
        int[] A = new int[max];
        for (int i = 0; i < n; i++)
            A[in.readInt()]++;
        int[] pr = new int[max];
        int[] P = new int[max];
        int[] id = new int[max];
        for (int i = 0; i < max; i++)
            pr[i] = i;
        for (int i = 2; i * i < max; i++)
            if (pr[i] == i)
                for (int j = i * i; j < max; j += i)
                    pr[j] = i;
        int cnt = 0;
        for (int i = 2; i < max; i++)
            if (pr[i] == i) {
                P[cnt] = i;
                id[i] = cnt++;
            }
        long[] C = new long[cnt];
        int all = 0;
        for (int i = max - 1; i > 1; i--) {
            all += A[i];
            int temp = i;
            while (temp > 1) {
                C[id[pr[temp]]] += all;
                temp /= pr[temp];
            }
        }
        long lo = 1;
        long hi = (long) 1e14;
        long ans = -1;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            boolean can = true;
            for (int i = 0; i < cnt && can && C[i] > 0; i++) {
                long temp = 0;
                long p = P[i];
                while (p <= mid) {
                    temp += mid / p;
                    p *= P[i];
                }
                can &= temp >= C[i];
            }
            if (can) {
                ans = mid;
                hi = mid - 1;
            } else
                lo = mid + 1;
        }
        System.out.println(ans);
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1000];
    private int curChar, numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    private int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String readString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    private boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private String readLine0() {
        StringBuffer buf = new StringBuffer();
        int c = read();
        while (c != '\n' && c != -1) {
            buf.appendCodePoint(c);
            c = read();
        }
        return buf.toString();
    }

    public String readLine() {
        String s = readLine0();
        while (s.trim().length() == 0)
            s = readLine0();
        return s;
    }

    public String readLine(boolean ignoreEmptyLines) {
        if (ignoreEmptyLines)
            return readLine();
        else
            return readLine0();
    }

    public char readCharacter() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public double readDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, readInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }
}