There is a highway which has 3 lanes. There is a list of N cars that enter the highway one by one. While entering the highway, each car can choose which lane to enter. However, once it enters a lane, it cannot change lanes.
Each car has a preferred speed, and will drive at that speed unless the car ahead of it (in its lane) is driving at a slower speed. If the car ahead is driving slower, the car will be forced to drive at the same speed as car ahead and the driver will not be happy. The first car to enter each lane will drive at its preferred speed.
Given an assignment of all cars to lanes, unhappy drivers are those who cannot drive at their preferred speed. Given the preferred speed of each car, find the minimum and maximum number of drivers that can be unhappy in any assignment.
Input Format
The first line has T, the number of test cases.
Each test case starts with a number N, the number of cars.
The next line has N space separated integers, the preferred speed of all cars in the order they enter the highway.
Constraints
1 <= T <= 100
1 <= N <= 500
0 <= speed of any car <= 10^9
Output Format
Output T lines, each having 2 numbers - the minimum and maximum number of unhappy drivers.
Sample Input 0
1
9
1 5 1 4 2 1 3 4 1
Sample Output 0
1 5
Explanation 0
Minimum number of unhappy people = 1.
lane 1: 4 3 1
lane 2: 5 2 1
lane 3: 1 1 4
In the above arrangement, 4 is the only unhappy person because he has to drive at speed 3
Maximum number of unhappy people = 5, when everyone is in the same lane.