Дана последовательность попарно различных чисел A = [ A 1 , A 2 , ..., A N ] , требуется переставить числа так, чтобы было верно A 1 < A 2 < ... < A m > A m + 1 > ... > A N (где m лежит между 1 и N включительно) Переставлять можно только пары соседних чисел, требуется минимизировать количество обменов.
1 ≤ A i ≤ 10 9 1 ≤ N ≤ 1000 A i попарно различны.
В задаче есть две группы тестов:
1.
1 ≤
N
≤ 10
- оценивается в 35 баллов
2.
1 ≤
N
≤ 1000
- оценивается в 65 баллов
В первой строке число N . Вторая строка содержит N чисел: A 1 , ..., A N .
Выведите одно число - минимальное количество обменов
3 1 2 3
0
5 1 8 10 3 7
1