Mahmoud has an array a consisting of n integers. He asked Ehab to find another array b of the same length such that:
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}.
5
2 3 5 4 13
2 3 5 7 11
3
10 3 7
10 3 7
Note that in the second sample, the array is already pairwise coprime so we printed it.
Name |
---|