#967. 希蒙的旋转

希蒙的旋转

题目背景

我们称一个数列 pp 是一个长度为 nn 的排列,当且仅当 pp 满足如下条件:

  1. pp 的长度为 nn
  2. 1,2,3,n1, 2, 3, \dots nnn 个数在 pp 中均恰好出现一次。

题目描述

对于一个排列 pp,定义一次“shift”操作是指:将 pp 里的每一个数字都依次向后移动一位,并把 pp 的最后一个数字移动到开头去。

例如,若排列 pp 初始时为 [1,4,2,3][1,4,2,3],则“shift”一次以后将变为 [3,1,4,2][3,1,4,2]

现在,给定一个长度为 nn 的排列 pp,请你按照如下规定循环操作:

  1. 对当前的排列 pp 做一次“shift”操作;
  2. 输出本次“shift”以后的排列 pp
  3. 判断排列 pp 的最后一个数字是否是 nn,如果是,则结束循环操作;否则回到 11 继续操作。

提示:请严格按照题目给出的顺序进行循环操作。

输入格式

第一行是一个整数,表示排列 pp 的长度 nn
第二行有 nn 个整数表示排列 pp,第 ii 个整数表示 pip_i

输出格式

对于每次操作的第二条“输出”操作,请你输出一行 nn 个整数,按顺序表示当前排列的每个数,一行中相邻两个数之间用一个空格隔开。

样例 #1

样例输入 #1

4
1 4 2 3

样例输出 #1

3 1 4 2
2 3 1 4

样例 #2

样例输入 #2

3
1 2 3

样例输出 #2

3 1 2
2 3 1
1 2 3

样例 #3

样例输入 #3

10
1 7 6 5 8 4 3 9 10 2

样例输出 #3

2 1 7 6 5 8 4 3 9 10

提示

样例 2 解释

p=[1,2,3]p = [1, 2, 3],按如下顺序进行循环操作:

  1. 进行一次“shift”操作,pp 变为 [3,1,2][3,1,2]
  2. 输出当前的排列 pp,故输出第一行为 3 1 2
  3. 判断 p3=23p_3 = 2 \neq 3,故继续循环操作;
  4. 进行一次“shift”操作,pp 变为 [2,3,1][2,3,1]
  5. 输出当前的排列 pp,故输出第二行为 2 3 1
  6. 输出判断 p3=13p_3 = 1 \neq 3,故继续循环操作;
  7. 进行一次“shift”操作,pp 变为 [1,2,3][1,2,3]
  8. 输出当前的排列 pp,故输出第二行为 1 2 3
  9. 输出判断 p3=3=3p_3 = 3 =3,故停止循环;

数据规模与约定

各测试点的信息如下表: | 测试点编号 | n=n = | 特殊约定 | | :-: | :-: | :-: | | 11 | 11 | 无| | 22 | 22 | 无 | | 33 | 33 | 无 | | 464 \sim 6 | 20002000 | pn1=np_{n - 1} = n | | 7107 \sim 10 | 20002000 | 无 |

对全部的测试点,保证 1pin20001 \leq p_i \leq n \leq 2000pp 是长度为 nn 的排列。