Mahmoud has an array a consisting of n integers. He asked Ehab to find another array b of the same length such that:

  b is lexicographically greater than or equal to a.  b_{i} ≥ 2.  b is pairwise coprime: for every 1 ≤ i < j ≤ n, b_{i} and b_{j} are coprime, i. e. GCD(b_{i}, b_{j}) = 1, where GCD(w, z) is the greatest common divisor of w and z. 

Ehab wants to choose a special array so he wants the lexicographically minimal array between all the variants. Can you find it?

An array x is lexicographically greater than an array y if there exists an index i such than x_{i} > y_{i} and x_{j} = y_{j} for all 1 ≤ j < i. An array x is equal to an array y if x_{i} = y_{i} for all 1 ≤ i ≤ n.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5), the number of elements in a and b.

The second line contains n integers a_1, a_2, ..., a_{n} (2 ≤ a_{i} ≤ 10^5), the elements of a.


-----Output-----

Output n space-separated integers, the i-th of them representing b_{i}.


-----Examples-----
Input
5
2 3 5 4 13

Output
2 3 5 7 11 
Input
3
10 3 7

Output
10 3 7 


-----Note-----

Note that in the second sample, the array is already pairwise coprime so we printed it.

Difficulty: HARD
Tags: Greedy algorithms

Number theory

Mathematics

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
MAX_NUM = 2000000
prime_str = '2      3      5      7     11     13     17     19     23     29 ' + '31     37     41     43     47     53     59     61     67     71 ' + '73     79     83     89     97    101    103    107    109    113 ' + '127    131    137    139    149    151    157    163    167    173 ' + '179    181    191    193    197    199    211    223    227    229 ' + '233    239    241    251    257    263    269    271    277    281 ' + '283    293    307    311    313    317 '
prime_list = [int(p) for p in prime_str.split()]
used = [False] * MAX_NUM
n = int(input())
a = list(map(int, input().split()))

def record(x):
	t = []
	for p in prime_list:
		if x % p == 0:
			while x % p == 0:
				x = x // p
			t.append(p)
			if x == 1:
				break
	if x != 1:
		t.append(x)
	for ti in t:
		for i in range(ti, MAX_NUM, ti):
			used[i] = True
b = []
for ai in a:
	if not used[ai]:
		b.append(ai)
		record(ai)
	else:
		temp = ai + 1
		while used[temp]:
			temp += 1
		b.append(temp)
		record(temp)
		break
temp = 2
while len(b) < len(a):
	while used[temp]:
		temp += 1
	b.append(temp)
	record(temp)
print(' '.join((str(x) for x in b)))


import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
ppp = '2      3      5      7     11     13     17     19     23     29 ' + '31     37     41     43     47     53     59     61     67     71 ' + '73     79     83     89     97    101    103    107    109    113 ' + '127    131    137    139    149    151    157    163    167    173 ' + '179    181    191    193    197    199    211    223    227    229 ' + '233    239    241    251    257    263    269    271    277    281 ' + '283    293    307    311    313    317 '
pp = [int(x) for x in ppp.split()]
xx = [False] * 1500000

def f(aa):
	t = []
	for p in pp:
		if aa % p == 0:
			while aa % p == 0:
				aa = aa // p
			t.append(p)
			if aa == 1:
				break
	if aa != 1:
		t.append(aa)
	for tt in t:
		for i in range(tt, 1500000, tt):
			xx[i] = True

def main():
	n = input()
	a = [int(x) for x in input().split()]
	b = []
	for aa in a:
		if xx[aa] == False:
			b.append(aa)
			f(aa)
		else:
			kk = aa + 1
			while xx[kk] == True:
				kk += 1
			b.append(kk)
			f(kk)
			break
	t = 2
	while len(b) < len(a):
		while xx[t] == True:
			t += 1
		b.append(t)
		f(t)
	print(' '.join((str(x) for x in b)))
main()


import sys
import math

def sieve(n):
	prime_factors = [[] for i in range(n + 1)]
	tmp = [True] * (n + 1)
	tmp[0] = tmp[1] = False
	for i in range(2, n + 1):
		if tmp[i]:
			for k in range(i, n + 1, i):
				tmp[k] = False
				prime_factors[k].append(i)
	return prime_factors
n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split(' ')))
b = []
forbidden_factors = set({})
prime_factors = sieve(2000005)
is_greater = False
min_available = 2
for ai in a:
	factors = prime_factors[ai]
	if not is_greater:
		curr = ai
		ok = True
		for f in factors:
			if f in forbidden_factors:
				ok = False
				break
		if ok:
			for f in factors:
				forbidden_factors.add(f)
		else:
			is_greater = True
			ok = False
			while not ok:
				curr += 1
				ok = True
				factors = prime_factors[curr]
				for f in factors:
					if f in forbidden_factors:
						ok = False
						break
			for f in factors:
				forbidden_factors.add(f)
	else:
		curr = min_available
		ok = True
		factors = prime_factors[curr]
		for f in factors:
			if f in forbidden_factors:
				ok = False
				break
		while not ok:
			curr += 1
			ok = True
			factors = prime_factors[curr]
			for f in factors:
				if f in forbidden_factors:
					ok = False
					break
		min_available = curr
		for f in factors:
			forbidden_factors.add(f)
	b.append(str(curr))
print(' '.join(b))


m = 2 * 10 ** 6
prime = [0 for i in range(m)]
n = int(input())
arr = list(map(int, input().split()))
s = set(arr)
i = 0
flag = 0
for i in range(n):
	jump = arr[i]
	if prime[jump] == 1:
		for k in range(jump, m):
			if prime[k] == 0:
				arr[i] = k
				flag = 1
				break
	s = set()
	l = 2
	jump = arr[i]
	while l * l <= arr[i]:
		while jump % l == 0:
			jump //= l
			s.add(l)
		l += 1
	if jump > 1:
		s.add(jump)
	for p in s:
		for j in range(p, m, p):
			prime[j] = 1
	if flag == 1:
		break
i += 1
for k in range(2, m):
	if i == n:
		break
	if prime[k] == 0:
		arr[i] = k
		for l in range(k, m, k):
			prime[l] = 1
		i += 1
print(*arr)


import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

def prime_list(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]

def prime_factors(n):
	if not hasattr(prime_factors, 'primes') or prime_factors.primes[-1] ** 2 < n:
		prime_factors.primes = prime_list(max(5000, int(n ** 0.5) + 1))
	res = []
	for p in prime_factors.primes:
		if p * p > n:
			break
		count = 0
		while n % p == 0:
			n //= p
			count += 1
		if count:
			res.append((p, count))
		if n == 1:
			break
	if n != 1:
		res.append((n, 1))
	return res

def update_available(n, available):
	pf = prime_factors(n)
	for (p, _) in pf:
		if available[p]:
			available[p::p] = [False] * ((len(available) - 1) // p)

def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	b = []
	available = [True] * 1500000
	for a_num in a:
		if available[a_num] == True:
			b.append(a_num)
			update_available(a_num, available)
		else:
			b_num = available.index(True, a_num)
			b.append(b_num)
			update_available(b_num, available)
			break
	b_num = 2
	while len(b) < n:
		b_num = available.index(True, b_num)
		b.append(b_num)
		update_available(b_num, available)
	print(' '.join((str(x) for x in b)))
main()


N = 2 * 10 ** 6
i = 2
p = [0 for i in range(N)]
while i * i <= N:
	if p[i] == 0:
		for j in range(i * i, N, i):
			p[j] = 1
	i += 1
a = []
for i in range(2, N):
	if p[i] == 0:
		a.append(i)
n = int(input())
l = list(map(int, input().split()))
d = dict()
ans = []
for i in range(n):
	v = []
	y = l[i]
	j = 2
	f = 1
	while j * j <= l[i]:
		if l[i] % j == 0:
			if j in d:
				f = 0
				break
			v.append(j)
			while l[i] % j == 0:
				l[i] /= j
		j += 1
	if l[i] > 1:
		if l[i] in d:
			f = 0
		v.append(l[i])
	if f == 1:
		ans.append(y)
		for x in v:
			d[x] = 1
	else:
		for x in range(y, N):
			j = 2
			f = 1
			l[i] = x
			while j * j <= l[i]:
				if l[i] % j == 0:
					if j in d:
						f = 0
						break
					while l[i] % j == 0:
						l[i] /= j
				j += 1
			if l[i] > 1:
				if l[i] in d:
					f = 0
			if f == 1:
				ans.append(x)
				break
		break
j = 2
x = ans[-1]
while j * j <= x:
	if x % j == 0:
		d[j] = 1
		while x % j == 0:
			x /= j
	j += 1
if x > 1:
	d[x] = 1
sz = len(ans)
for i in a:
	if sz == n:
		break
	if i not in d:
		ans.append(i)
		sz += 1
for i in ans:
	print(i, end=' ')
print()