C. Сортировка вставками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Петя — начинающий программист. Он уже освоил базовые возможности языка 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.

Входные данные

В первой строке записано единственное целое число n (2 ≤ n ≤ 5000) — количество чисел в перестановке. Во второй строке содержатся n различных целых чисел от 0 до n - 1 включительно — сама перестановка.

Выходные данные

Выведите два целых числа: минимальное количество вызовов функции swap и количество таких пар (i, j), что обмен элементов входной перестановки с индексами i и j позволяет достичь этого минимального количества вызовов.

Примеры
Входные данные
5
4 0 3 1 2
Выходные данные
3 2
Входные данные
5
1 2 3 4 0
Выходные данные
3 4
Примечание

В первом примере подходят пары (0, 3) и (0, 4).

Во втором примере подходят пары (0, 4), (1, 4), (2, 4) и (3, 4).