В Самую Секретную Военную Часть под командованием полковника Покрышкина приехал с проверкой генерал из Министерства Обороны. По этому случаю полковник приказал всем n солдатам из своей Части построиться на плацу.
Согласно военному уставу, солдаты должны стоять в порядке невозрастания их роста, но так как времени на построение совсем не осталось, то солдаты выстроились в произвольном порядке. Однако у генерала весьма плохое зрение, и поэтому он считает, что солдаты построены правильно, если самый первый в строю — солдат с максимальным ростом, а самый последний — солдат с минимальным ростом. Обратите внимание, что неважно то, как расположены остальные солдаты, в том числе и в случае нескольких максимальных или минимальных по росту солдат. Важны лишь росты первого и последнего солдата.
Например, генерал считает последовательность ростов (4, 3, 4, 2, 1, 1) правильной, а последовательность (4, 3, 1, 2, 2) — нет.
За одну секунду полковник может обменять местами любых двух соседних солдат. Помогите ему подсчитать, какое минимальное количество секунд понадобится, чтобы получившийся строй понравился генералу.
Примечание
В первом примере полковнику нужно поменять местами первого и второго солдата, а затем третьего и четвертого — это займет 2 секунды. Итоговое положение солдат: (44, 33, 22, 11).
Во втором примере полковник может производить обмены в следующей последовательности:
- (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)