Part 14 of 15 in Sorting  

The Best Pivot by phantom11

Problem statement

Quick Sort as we know can take different amount of time to sort an array based on the pivot element we choose for sorting. In this problem, we try to learn to implement quick sort by comparing the first index and last index as our pivot. Given an array N, you need to find the number of swaps required to sort the array using quick sort algorithm taking the first element and the last element of the sub arrays as the pivot everytime.

Input

First line of the input contains the number of test cases T. T test cases follow. The first line of each test case contains the N, (1 ≤ N ≤ 50) the number of integers in the array. The second line contains N space separated integers. All N numbers are distinct.

Output

For each test case, print on one line two numbers, the number of swaps (minimum) to sort the given array in ascending order using quick sort by taking the first element as pivot, followed by a space, and then the number of swaps by taking the last element as pivot.

Sample Input
2
3
4 2 5
5
10 11 8 7 1
Sample Output
1 1
3 5


To try out your code



Sign in

Sign up