A11734 | Mahmoud and Ehab and another array construction task

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$ .

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 $n$ space-separated integers, the $i$ -th of them representing $b_{i}$ .