Петя — начинающий программист. Он уже освоил базовые возможности языка C++ и приступил к изучению алгоритмов. Первым алгоритмом, с которым он познакомился, стала сортировка вставками. Петя уже написал код, реализующий этот алгоритм и сортирующий по неубыванию заданный целочисленный ноль-индексированный массив a размера n.

for (int i = 1; i < n; i = i + 1)
{
   int j = i; 
   while (j > 0 && a[j] < a[j - 1])
   {
      swap(a[j], a[j - 1]); // поменять местами элементы a[j] и a[j - 1]
      j = j - 1;
   }
}

Петя подает на вход этого алгоритма исключительно массивы, являющиеся перестановками чисел от 0 до n - 1. Он уже выбрал перестановку, которую хочет отсортировать, но решил предварительно поменять местами какие-то два её элемента. Петя хочет выбрать эти элементы таким образом, чтобы количество вызовов функции swap, выполняемых сортировкой, было минимальным. Помогите Пете определить, каким количеством способов можно выполнить обмен с соблюдением этого требования.

Гарантируется, что во входной перестановке всегда можно поменять местами два элемента таким образом, чтобы уменьшилось количество вызовов функции swap.