Arrival of the General
国防部派一位将军前来视察由 SuperDuper 上校管辖的绝密特种部队。得知消息后,上校命令 名士兵到阅兵场列队。
军队条例要求士兵按身高非递增的顺序排队。但时间非常紧张,士兵现在是任意顺序站成一排。这位将军视力不好,他判定队列合格的标准是:队列第一个士兵身高为最大值,最后一个士兵身高为最小值。中间士兵的排列不作要求;允许存在多个最大值、多个最小值,只关心队首和队尾。
例如:序列 将军认为是合格的;而 是不合格的。
上校每一秒可以交换任意两个相邻士兵。请计算,最少需要多少秒,调整出一将军认可的队列。
第一行一个整数 ,代表士兵人数。
第二行 个整数 ,代表从队头到队尾每个士兵的身高,数字之间空格分隔,身高允许重复。
输出一个整数:上校调整队列所需要的最少秒数。
4 33 44 11 22
2
7 10 10 58 31 63 40 76
10
样例1:交换1、2号;交换3、4号,耗时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)

