1545. [UVa 1402] 机器排序

【题目描述】

在布拉格捷克理工大学（Czech Technical University）某个幽深的角落，有一些实验室用来检测各种材料的机械和电气性能。在昨天的一项展示中，你已经见识了其中的一间是如何变成全新的多媒体实验室的。但那里仍然有别的实验室，服务于它们最初的用途。

在这个任务中，你将要给这样的一间实验室中一个搬运样品的机器人编写程序。设想有一些材料样品在一条传送带上排成一排。这些样品有不同的高度，这可能会给接下来的处理带来麻烦。为了消除这样的隐患，我们需要将这些样品按高度升序排列。

排序由一条机械臂完成，它可以抱起一些连续的样品并且将它们掉头，这样一来它们在传送带上的顺序就被翻转。换句话说，一个操作可以翻转A到B（含两端）的样品顺序。

给样品排序的一个可能方式是找到高度最小的样品P1，将1到P1的样品顺序翻转。这将使得P1成为第一个样品。接下来我们找到高度第二小的样品P2，将2到P2的样品顺序翻转。然后找到高度第三小的样品，以此类推。

这张图片展示了一个含6个样品的简单例子。高度最小的样品在4号位置，因此机械臂旋转前4个样品。高度第二小的样品在6号位置，因此下一个操作是翻转2-6号样品位置。第三步是翻转3-4号样品位置，以此类推。

你的任务是找到用上述算法给样品排序时正确的翻转操作序列。如果不止一个样品有相同的高度，必须保持它们的顺序不变：在初始序列中靠前的在最终序列中也应该靠前。

【输入格式】

输入包含多组数据。

每组数据有两行。第一行是一个正整数N，即样品个数（1<=N<=100000）。

第二行有N个由空格分隔的正整数，即各样品的高度，按最初的样品顺序给出。

输入结束标志为一行一个0。

【输出格式】

对每组数据，输出一行恰好N个整数P1,P2,...,PN，彼此由空格分隔。每个Pi应该是一个正整数（1<=Pi<=N），给出了第i次翻转操作前第i个样品的位置。

注意如果一个样品已经站在了正确的位置Pi上，你也应该输出Pi，表明“Pi到Pi的样品”（即Pi一个样品）应该被翻转。

【样例输入】

6
3 4 5 1 6 2
4
3 3 2 1
0

【样例输出】

4 6 4 5 6 6
4 2 4 4 

【来源】

Central Europe Regional Contest 2007 Robotic Sort

UVa 1402 Robotic Sort