Steve's perfectionism

Interview

Time limit1sMemory limit256 MB

Summary

Given an array of positive integers, output a strictly increasing array of the same length where each element is a multiple of the matching input element, at most 1e9.

Level: Medium4 of 10
Topics: Greedy, Math
Solved: No attempts yet

Problem

Steve is a hopeless perfectionist. He keeps running into arrays of positive integers, and he does not always enjoy what he sees. Steve likes an array if and only if it is strictly ascending. An array he does not like must be changed right away, or Steve will be disappointed.

A new array satisfies Steve only if it keeps the original length and each element is divisible by the corresponding element of the old array. An array that already pleases him can be left alone, or changed anyway.

Input

The first line contains a single integer $n$ ( $2 \le n \le 1000$ ). The second line contains $n$ space-separated positive integers $a_i$ ( $1 \le a_i \le 10^6$ ).

Output

Print $n$ positive integers $a_i$ ( $1 \le a_i \le 10^9$ ), the new array that Steve will like. If several solutions exist, print any of them.

Examples1

Example 1
Input
```
7
1 10 5 4 3 2 7
```
Expected output
```
1 10 15 20 30 32 35
```