Bottle Necks

There are N bottles. ith bottle has A[i] radius. Once a bottle is enclosed inside another bottle, it ceases to be visible. Minimize the number of visible bottles.

You can put ith bottle into jth bottle if following condition is fulfilled:

• ith bottle itself is not enclosed in another bottle.
• jth bottle does not enclose any other bottle.
• Radius of bottle i is smaller than bottle j (i.e. A[i] < A[j]).

Constraints

• 1 <= N <= 100000
• 1 <= A[i] <= 1018

Input Format

• First line contains T, the number of test cases. For each test case:
• First line contains a single integer N denoting the number of bottles
• Second line contains N space separated integers, ith integer denoting the radius of ith bottle.
• (1 <= i <= N)

Output

• Minimum number of visible bottles after all the operations

Example Input

2
8
1 1 2 3 4 5 5 4
5
5 7 1 2 4

Output:

2

1

Solution:

t=int(input()) #bottle neck with dictionary (NO TIME COMPLEXITY)

for i in range(t):

    n=int(input())

    a=list(map(int,input().split()))

    m = dict() 

    ans = 0

    for i in range(n): 

        m[a[i]]=0

    for i in range(n):

        m[a[i]] = m[a[i]]+ 1

        

        ans = max(ans, m[a[i]]) 

    print(ans)