VISIBLEBOX  Decreasing Number of Visible Box
Shadowman loves to collect box but his roommates woogieman and itman don't like box and so shadowman wants to hide boxes as many as possible. A box can be kept hidden inside of another box if and only if the box in which it will be held is empty and the size of the box is at least twice as large as the size of the box.
Print the minimum number of box that can be shown.
Input
The input set starts with single line integer T (1<=T<=50) the number of test cases. Then following T cases starts with an integer N (1<=N<=100000) denoting the number of box. The next line contains N space separated positive integer. ith of them contains a numbers A_{i}(1<=A_{i}<=100000) size of the ith box.
Output
Output the the case number and the minimum number of box that can be shown.
Example
Input: 2 4 1 2 4 8 4 1 3 4 5 Output: Case 1: 1 Case 2: 3
hide comments
shub1025:
20180109 11:57:35
Thank You @shubhamGupta for the test cases 

Admin Deepak Baghel:
20160612 16:22:02
Easy O(max(A(i))) solution :) 

Baojun Wang:
20160131 08:46:17
time limit too strict except c/c++ Last edit: 20160131 08:46:48 

manitejavarma:
20151223 12:54:25
Is the given input sorted or not?


gomathi ganesan:
20151207 12:47:49
Last edit: 20151231 07:43:17 

Vipul Srivastava:
20151203 10:08:36
Last edit: 20151203 10:32:35 

Shubham Gupta:
20151202 05:38:45
Few points to be noted: The input array given is not in sorted order. Do maintain a tag/index/map for a counter of each element.

Added by:  imranziad 
Date:  20151125 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  AIUB CS Fest 2015 (Mokaddesh Rashid Shovon) 