将军的到来


Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 4M

Author:
Problem type
Allowed languages
C++

将军的到来

一个国防部派遣了一名将军去视察由超级上校指挥的超级秘密军事小队。得知这一消息后,上校命令所有的 \(n\) 名士兵站成队列。 根据军事章程,士兵应该按照身高的非递增顺序排列。但由于时间紧迫,士兵们站成了一个任意的顺序。然而将军的视力较差,他认为如果队列中的第一个士兵身高最大,最后一个士兵身高最小,那么队列就是正确的。注意,其他士兵的位置并不重要,包括当有多个士兵身高最大或最小时,只有队列的第一个和最后一个士兵的身高是关键。

例如,将军认为身高序列 (4, 3, 4, 2, 1, 1) 是正确的,而 (4, 3, 1, 2, 2) 是错误的。

在一秒钟内,上校可以交换任意两个相邻的士兵。帮助上校计算形成一个将军会认为正确的队列所需要的最短时间。

输入

第一行包含一个整数 \(n\) (\(2 \le n \le 100\)),表示队列中的士兵数量。 第二行包含 n 个整数 a1, a2, ..., an (\(1 \le ai \le 100\)),表示士兵的身高,按士兵从队列开始到队列末尾的顺序排列,数值之间用空格分隔。a1, a2, ..., an 不一定相同。

输出

输出一个整数,表示将军会满意的队列排列所需要的最小时间(单位:秒)。

输入 1:
4
33 44 11 22
输出 1:
2
输入 2:
7
10 10 58 31 63 40 76
输出 2:
10
说明

示例 1: 在第一个示例中,上校需要交换第一个和第二个士兵的位置,然后交换第三个和第四个士兵的位置。这样需要 2 秒钟。最终士兵的排列为 (44, 33, 22, 11)。
示例 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)

需要交换 10 次才能使队列符合将军的要求。


Comments

There are no comments at the moment.