Recently you are into eCommerce sites. You sell useless (which you don’t need) stuffs and try to get absurdly high prices for them through online bidding. For the particular e-commerce site you use for selling, the online bidding follows this rule:
You open bidding for an item you wish to sell. Potential buyers try to bid the highest amount and normally after a set period of time, the highest bidder acquires the product. You can also stop the bidding at any time you want and declare the current highest bidder as the winner. This site also has an insurance system which states that, if the highest bidder declines to buy the product after the bidding has ended, the next highest bidder will get a chance to buy it and so on. If all the bidders up until the median bid for that product declines to buy, the site itself will buy it at the median amount among the bids for that product.
You are a clever fellow and want to earn as much money as possible from a bidding. You have somehow (either through deep learning or by consulting with an oracle) managed to get all the bids for your product before the bidding even started. Now you want to stop the bidding at the earliest of such a time that will maximize the median bid amount.
Input
Input starts with an integer T (≤ 150), denoting the number of test cases. Each case starts with an integer N (1 ≤ N ≤ 100000), the total number of bids that will happen if you don’t stop the bidding before it’s end-time. Followed by N integers, B0, B1, B2 … BN-1, where Bi (1 ≤ Bi ≤ 100000) is the amount of the ith bid.
Output
You have to output the earliest index of the bid after which you will stop the bidding to maximize the median bid amount. Index of the bid is zero (0) based.
Sample
| Input | Output |
|---|---|
2 3 1 2 3 1 10 | Case 1: 2 Case 2: 0 |
Definition of median:
The median of a finite list of numbers can be found by arranging all the numbers from smallest to greatest.
If there is an odd number of numbers, the middle one is picked.
If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values.
