Mahmoud and Ehab and another array construction task

3000ms

262144K

Description:

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⁵), the number of elements in a and b.

The second line contains n integers a₁, a₂, ..., a_n (2 ≤ a_i ≤ 10⁵), the elements of a.

Output:

Output n space-separated integers, the i-th of them representing b_i.

Sample Input:

5
2 3 5 4 13

Sample Output:

2 3 5 7 11

Sample Input:

3
10 3 7

Sample Output:

10 3 7

Note:

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

Informação

Provedor Codeforces

Código CF959D