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.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		(new Main()).solve();
	}

	public Main() {
	}
	
	MyReader in = new MyReader();
	// Scanner in;
	PrintWriter out = new PrintWriter(System.out);
	
	void solve() throws IOException {
		//BufferedReader in = new BufferedReader(new
		//InputStreamReader(System.in));
		//Scanner in = new Scanner(System.in);
		//in = new Scanner(new FileReader("input.txt"));
		int n = in.nextInt();		
	
		long startTime = System.currentTimeMillis();
		
		int[] p = new int[664579];
		int[] a = new int[10000001];
		Arrays.fill(a, -1);
		for (int i = 2, index = 0; i < a.length; i++) {
			if (a[i] != -1) {
				continue;
			}
			p[index] = i;
			for (int j = i; j < a.length; j += i) {
				a[j] = index;
			}
			index++;
		}
		long[] pow = new long[664579];
		long[] cnt = new long[10000001];
		for (int i = 0; i < n; i++) {
			int ai = in.nextInt();
			cnt[1]++;
			if (ai + 1 < cnt.length) {
				cnt[ai + 1]--;
			}
		}
		for (int i = 2; i < cnt.length; i++) {
			cnt[i] += cnt[i - 1];
			for (int j = i; j > 1; j /= p[a[j]]) {
				pow[a[j]] += cnt[i];
			}
		}
		long d = 1, u = Long.MAX_VALUE / 2, res = u;
		while (d <= u) {
			long mid = (d + u) / 2;
			boolean g = true;
			for (int i = 0; i < p.length; i++) {
				int prime = p[i];
				long t = mid;
				long c = 0;
				while (t > 0) {
					t /= prime;
					c += t;
				}
				if (c < pow[i]) {
					g = false;
					break;
				}
			}
			if (g) {
				res = mid;
				u = mid - 1;
			} else {
				d = mid + 1;
			}
		}
		out.println(res);
		out.close();
		
		System.err.println(System.currentTimeMillis() - startTime);
		
	}	
		
};

class MyReader {
	private BufferedReader in;
	String[] parsed;
	int index = 0;

	public MyReader() {
		in = new BufferedReader(new InputStreamReader(System.in));
	}

	public int nextInt() throws NumberFormatException, IOException {
		if (parsed == null || parsed.length == index) {
			read();
		}
		return Integer.parseInt(parsed[index++]);
	}

	public long nextLong() throws NumberFormatException, IOException {
		if (parsed == null || parsed.length == index) {
			read();
		}
		return Long.parseLong(parsed[index++]);
	}
	
	public String nextString() throws IOException {
		if (parsed == null || parsed.length == index) {
			read();
		}
		return parsed[index++];
	}

	private void read() throws IOException {
		parsed = in.readLine().split(" ");
		index = 0;
	}

	public String readLine() throws IOException {
		return in.readLine();
	}
};