s-quark去参加一个排序比赛,比赛的规则是:每人写一个排序程序,将一列无序的数字按从小到大排好序。当两个人对决时,可以互相出测试数据,每个人都要使用对方出的数据运行程序,耗时短者胜利。
现在,s-quark拿到了对方的程序,发现对方写的是使用随机化交换写法的快速排序,并且,对方的随机函数rand()并没有使用时间作为种子,也就是说,该rand()函数产生的伪随机数是可以被预测的。
s-quark希望该程序在运行时,每次都是以l到r范围内的最大元素为作为划分基准,这样就可以使快速排序达到最大比较次数。s-quark很快设计出了这样的序列,从而轻松赢得了比赛。而你的任务是,对于给定的数字数量n(n <= 100000),和伪随机数序列,找出一个1到n的排列,使得给定的快速排序程序每次都是以l到r范围内的最大元素作为基准进行划分。如果有多个排列满足要求,输出字典序更小的排列。
输入的第一行为一个正整数,为题目描述中的n。
接下来一行包含n个正整数,为题目描述中的伪随机数序列。该序列当用到超过n次随机数时,会从序列的第1个整数重新开始。
输出一行,包含n个正整数,为题目所求的1到n的排列。
请输入正确的证书编号
学员姓名:孙兴民
课程:Scratch Level 1
发证日期:2019.08.15