#5846. 将军的到来
将军的到来
题目描述
国防部派了一名将军去视察由超级杜珀上校指挥的超级秘密军事小队。得知这个消息后,上校命令所有士兵在阅兵场列队。
根据军事宪章,士兵应按身高不增高的顺序站立。但由于几乎没有时间这样做,士兵们排成了任意的顺序。然而,将军相当短视,他认为如果队列中第一个士兵的高度最大,最后一个士兵的高度最小,那么士兵们就排对了。
请注意,其他士兵的位置并不重要,包括当有几个士兵的高度是最大或最小的情况下。只有第一个和最后一个士兵的高度才是重要的。
例如,一般认为高度序列 (4, 3, 4, 2, 1, 1) 是正确的,序列 (4, 3, 1, 2, 2) 是错误的。
在一秒钟内,上校可以交换任何两个相邻的士兵。求最少经过多少时间可以保证列队第一个人最高,最后一个人最矮。
输入格式
- 第一行输入数字 ()
- 第二行依次输入 ()
输出格式
输出最小的调整队形的时间(即交换的次数)
输入样例 #1
4
33 44 11 22
输出样例 #1
2
输入样例 #2
7
10 10 58 31 63 40 76
输出样例 #2
10
题目说明
对于样例2,整个交换过程为:
(10, 10, 58, 31, 63, 40, 76) (10, 58, 10, 31, 63, 40, 76) (10, 58, 10, 31, 63, 76, 40) (10, 58, 10, 31, 76, 63, 40) (10, 58, 31, 10, 76, 63, 40) (10, 58, 31, 76, 10, 63, 40) (10, 58, 31, 76, 63, 10, 40) (10, 58, 76, 31, 63, 10, 40) (10, 76, 58, 31, 63, 10, 40) (76, 10, 58, 31, 63, 10, 40) (76, 10, 58, 31, 63, 40, 10)