Код Дробарки
Уеслі Крушер працює асистентом і веде курс "Вступ до алгоритмів". Під час першого заняття студентів попросили придумати власні алгоритми сортування. Монті запропонував наступний код:
Натхненний Карлос представив наступний код:
Уеслі хоче визначити, чий алгоритм є кращим.
Для заданого вхідного масиву, що містить до 8 значень, обчисліть і виведіть очікувану кількість ітерацій для кожного алгоритму. Тобто, скільки ітерацій у середньому має виконати кожен алгоритм для даного вводу?
Вхідні дані
Перша строка містить кількість тестів t (2 ≤ t ≤ 100). Кожен тест задається в окремому рядку. Першим у рядку йде кількість елементів у масиві n (2 ≤ n ≤ 8). Далі у рядку задані n цілих чисел. Числа знаходяться в діапазоні від 0 до 100 включно. Елементи масиву не обов'язково різні.
Вихідні дані
Для кожного тесту виведіть очікувану кількість ітерацій для алгоритму Монті та для алгоритму Карлоса, як показано у прикладі виходу. Між словами має бути рівно один пробіл, і не повинно бути пробілів на початку або в кінці кожного рядка. Має бути рівно шість цифр після десяткової крапки. Округлення повинно бути до найближчого значення, яке можна представити.