1546: 阿正的换位排序
题目描述
阿正在有了一定的算法知识后，不禁感慨到“排序真是个经典的问题！”。
这天阿正同学正在研究排序算法，他发现有交换元素的位置是完成排序的必要条件。所以阿正决定返璞归真，从交换相邻元素入手，完成排序过程。
但是阿正发现只交换相邻两个元素完成排序效率实在是太低了。不过没关系，“大部分高性能的算法都是从低性能算法的基础上优化而来的”你这样安慰阿正道。
但是阿正还是心怀不甘，说将一个长度为n的序列完成非递减排序一定可以在 [n*(n-1)]/2 -1 步内完成。但是你觉得这个结论明显是错误的，所以不甘心的阿正和你理论了起来。
阿正随机写下了若干个序列，你的任务是判断这若干个序列能否在 [n*(n-1)]/2 -1 步内完成排序。
输入
多实例输入
每组数据第一行一个正整数n，代表序列长度；（2<=n<=100000）
每组数据第二行包含n个非负整数，依次代表序列各元素。
测试数据保证全部样例n的和不超过100000，其他数据保证在整形范围内。
输出
每组数据对应一行。
若可以在规定步数内完成排序，请输入“Yes”，否则请输入“No”。（输出不带引号）
样例输入 复制
5
5 3 2 1 4
6
3 5 4 2 7 5样例输出 复制
Yes
Yes提示
对于第一组数据，可以按以下方案进行交换完成阿正的“换位排序”：
1 交换四号元素“1”与三号元素“2”：[5 3 2 1 4]->[5 3 1 2 4]
2 交换三号元素“1”与二号元素“3”：[5 3 1 2 4]->[5 1 3 2 4]
3 交换二号元素“1”与一号元素“5”：[5 1 3 2 4]->[1 5 3 2 4]
4 交换四号元素“2”与三号元素“3”：[1 5 3 2 4]->[1 5 2 3 4]
5 交换三号元素“2“与二号元素”5“：[1 5 2 3 4]->[1 2 5 3 4]
6 交换四号元素“3”与三号元素”5“：[1 2 5 3 4]->[1 2 3 5 4]
7 交换五号元素“4“与三号元素”5“：[1 2 3 5 4]->[1 2 3 4 5]
按上述步骤可以在最小的步数（共七步）内完成排序，由于n=5，[n*(n-1)]/2-1=9，七步小于九步，故输出Yes。