该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem F. 你说的对，但是我是线性复杂度

时间限制 : 1000 ms

空间限制 : 256 MB

题目背景

Bogo排序(Bogo-sort)，又被称为猴子排序，是一种恶搞排序算法，其算法就是将元素随机打乱，然后检查其是否符合排列顺序，若否，则继续进行随机打乱，继续检查结果，直到符合排列顺序。 Bogo排序的最坏时间复杂度 为O(∞)， 一辈子也不能输出排序结果，平均时间复杂度为 O(n·n!)。

不过好在量子物理的发展，给了我们用这个方法解决问题的一线生机。所谓量子猴排 （Quantum Bogo sort） 就是洗牌的时候，使用量子化随机排列（quantumly randomized）。这样的话，我们在观测这组数之前，这组数的状态是叠加的，通过这种量子化随机排列，我们划分出来了 $O(n!)$ 个平行宇宙。接下来，在某个宇宙00729中，观测一下这组数，发现运气不好，没有排序好，那么我们就销毁掉这个宇宙。然后再看看其他宇宙的运气怎么样。终于，在一个宇宙04008中，发现刚好是排好序的数组。那么我们就保留宇宙04008。最后，没有被销毁的宇宙中，数组都是恰好一次被排好序的。算法结束。

我们来分析一下量子猴排的时间复杂度，嗯，$O(n)$，看是不是快了很多。

题目描述

让我们用一种比较"现实"的方法在线性复杂度 $O(n)$ 内完成Bogo排序，首先我们先定义正常的Bogo排序流程：

以对一个长度为 $n$ 的整数数组排序为例，我们先定义一个函数，作用是根据一个下标设置随机数生成器种子，生成随机数，返回其模数组长度 $n$ 的结果。伪代码如下：

接下来，我们对数组中的数进行随机打乱。具体流程是，遍历数组中的每个数；对于一个下标 $i$ ，我们调用刚才的随机数生成函数，得到一个随机下标，然后将这个下标的数和原来下标 $i$ 的数进行交换。伪代码如下：

最后循环调用 $random\_shuffle$ 函数，直到数组有序。

理论上来说，只要我们 $gen(i, n)$ 函数的返回值足够巧妙，我们就可以通过只调用一次 $random\_shuffle(a, n)$ 函数完成对 $a$ 数组的排序。所以现在你的目标就是找到这一组 $gen(i, n)$ 的返回值使得只需要执行一次Bogo排序流程就可以让数组有序，实现线性复杂度的排序。

输入格式

第一行一个整数 $n$，代表数组长度；

第二行 $n$ 个整数，用空格隔开，代表数组 $a$ 中每个元素；

保证数组 $a$ 中的元素两两不相同。

输出格式

输出一行 $n$ 个整数，用空格隔开，代表一组巧妙的 $gen(i, n)$ 函数返回值。

如果有多种满足条件的返回值结果，输出其中一种即可。

样例输入

5
2 3 1 5 4

样例输出

1 1 0 4 4

样例解释

排序流程如下：

$swap(a[0], a[1])$，数组变为 $[3, 2, 1, 5, 4]$

$swap(a[1], a[1])$，数组变为 $[3, 2, 1, 5, 4]$

$swap(a[2], a[0])$，数组变为 $[1, 2, 3, 5, 4]$

$swap(a[3], a[4])$，数组变为 $[1, 2, 3, 4, 5]$

$swap(a[4], a[4])$，数组变为 $[1, 2, 3, 4, 5]$

数据范围与约定

$1 \le n \le 10^5$，数组中的每个元素满足 $1 \le a_i \le 10^6$。