思路：构造

对于每个 $a_i$ ，令 $r_i = a_i \mod i$ ，所以 $b_i \mod i = i - r_i$ 。

所以考虑 $b_i$ ，就枚举从 $i-r_i$ 开始，$i\times 2-r_i, i\times 3-r_i,...$ ，最多枚举到 $10^6$ 即可。

时间复杂度：$O(10^6 \times \log n)$

cpp

题目内容

小红有一个长度为 $n$ 的数组 $a$ ，他想让你用这个数组 $a$ 来构造一个长度同样为 $n$ 的数组 $b$ 。

你需要使得这个数组 $b$ 的每个元素值都在 $[1, 10^9]$ 之间，且所有元素各不相同。

此外，你还需要使得 $(a_i + b_i)\mod i = 0, (1\leq i\leq 10^9)$ 。

输入描述

第一行，一个整数 $n(1\leq n\leq 10^5)$ ，表示数组的长度。

第二行，$n$ 个数表示数组 $a$ 的 $n$ 个元素，第 $i$ 个元素 $a_i\in [1, 10^6]$

输出描述

一行，$n$ 个数表示构造出的数组 $b$ 。

样例

输入

5
1 2 3 4 5

输出

1 2 3 4 5