Submit Best Submissions All Submissions

483. Buildings Arrangement

Problem Statement:
We are going to build a huge city of N buildings, all N buildings will be built in one street next to each other.

You are given the heights of these buildings, and your task is to arrange them in a row. For example let's say this will be the height of the buildings when you arrange them in this order from left to right "1 3 2 5 4", if you look at the buildings from left to right, you won't see the building of height 2 (it's hidden behind the building of height 3), and you won't see the building of height 4 (it's hidden behind the building of height 5). But if you look from right to left, you will see the building of height 4, but still won't see the building of height 3. But if we consider the following arrangement "1 2 3 5 4", each building will be visible either from right or from left. Building X will be hidden behind building Y, if the height of X is less than or equal to the height of Y.

Given the heights of all buildings, your task is to arrange them in a way that minimizes the number of buildings which are not visible when you look from both sides.

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 100) representing the number of test cases. Followed by T test cases.

Each test case starts with a line containing an integer N (the number of buildings, 1 ≤ N ≤ 10,000).

Followed by N lines, each line contains the height of a building, each height will be a positive integer and it won't be more than 1,000,000,000 (the same height can be repeated, and the heights are not sorted in any way).

Output Format:
For each test case print a single line containing a single integer which is the minimum number of buildings which will be hidden in the best arrangement.

Sample Input:
2 5 1 3 2 5 4 3 3 3 3

Sample Output:
0 1

In the second test case, all buildings are of the same height, so the one in the middle will always invisible from both sides.

Added by: ahmed_aly
Added at: 2017-10-15 18:00:00 UTC
Time Limit: 2 seconds
Partial score: No
Source:A2OJ Code Battle Round 2