Задача library2016. Головний бібліотекар найбільшої бібліотеки світу вийшов на роботу після відпустки й з жахом побачив, що всі томи окраси бібліотеки – Збірка Всіх Творів Усіх Часів Та Народів – розставлені у довільному порядку. Він одразу заходився наводити порядок. Оскільки головний бібліотекар – літня людина, він не може переносити великий вантаж. Та, намагаючись якнайшвидше завершити справу, він кожного разу бере два сусідніх томи та переставляє обидва на інше місце, не змінюючи порядку слідування томів й не вставляючи між ними інших томів.
Визначити найменшу кількість таких перестановок, після якої всі томи славетної збірки стоятимуть у порядку зростання номерів.
Технічні умови. Програма library2016 читає з пристрою стандартного введення натуральне число n (2<n≤10) – кількість томів збірки всіх творів усіх часів та народів, а далі через пропуски n натуральних чисел – номери томів у тому порядку, в якому їх побачив бібліотекар. Гарантується, що всі томи від 1-го до n-го присутні в єдиному примірнику. Програма виводить на пристрій стандартного виведення мінімально можливу кількість перестановок пар сусідніх томів. Якщо такі перестановки не дозволяють впорядкувати всі томи збірки в порядку зростання їхніх номерів, вивести на стандартний пристрій виведення -1.
Приклади
Введення 3 1 2 3
Виведення 0
Введення 3 1 3 2
Виведення -1
Введення 5 5 4 3 2 1
Виведення 3
© LIKT 1998-2018