Question

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:

1) ith bottle itself is not enclosed in another bottle.

2) jth bottle does not enclose any other bottle.

3) Radius of bottle i is smaller than bottle j (i.e. A[i] < A[j]).

Constraints
1 <= N <= 100000.

1 <= A[i] <= 10^18.

Input Format
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.

Test Case

Explanation
Example 1

Input

8

1 1 2 3 4 5 5 4

Output

2

Explanation

1st bottle can be kept in 3 rd one 1-->2 , which makes following bottles visible [1,2,3,4,5,5,4]

similarly after following operations, the following will be the corresponding visible bottles

Operation ? Visible Bottles

2 ? 3 [1,3,4,5,5,4]

3 ? 4 [1,4,5,5,4]

4 ? 5 [1,5,5,4]

1 ? 4 [5,5,4]

4 ? 5 [5,5]

finally there are 2 bottles which are visible. Hence, the answer is 2

Answer 1

Answer:#include <stdio.h>

int main()

{

int n,a[100],b[100];

int t,i,j,c=0;

scanf("%d",&n);

for(i=0;i<n;i++)

scanf("%d",&a[i]);

for(i=0;i<n;i++)

for(j=0;j<n-1;j++)

{

if(a[j]>a[j+1])

{

t=a[j];

a[j]=a[j+1];

a[j+1]=t;

}

}

for(i=0;i<n-1;i++)

for(j=0;j<n;j++)

{

if(a[i]<a[j])

{

a[i]=0;

break;

}

}

for(i=0;i<n;i++)

if(a[i]>0)

c++;

printf("%d",c);

return 0;

}

Explanation: