John’s clothing store has a pile of loose socks where each sock is labeled with an integer, , denoting its color. He wants to sell as many socks as possible, but his customers will only buy them in matching pairs. Two socks, and , are a single matching pair if .

Given and the color of each sock, how many pairs of socks can John sell?

**Input Format**

The first line contains an integer, , denoting the number of socks.

The second line contains space-separated integers describing the respective values of .

**Constraints**

**Output Format**

Print the total number of *matching pairs* of socks that John can sell.

**Sample Input**

```
9
10 20 20 10 10 30 50 10 20
```

**Sample Output**

```
3
```

**Explanation**

As you can see from the figure above, we can match three pairs of socks. Thus, we print on a new line.

**Solution**

```
public static void main(String[] args) {
Scanner scan= new Scanner(System.in);
int n= scan.nextInt();
Map<Integer, Integer>pairs= new HashMap<Integer, Integer>();
int a[]= new int[n];
for(int i=0;i<n;i++)
{
a[i]=scan.nextInt();
if(pairs.containsKey(a[i]))
{
int val=pairs.get(a[i]);
pairs.remove(a[i]);
pairs.put(a[i],++val);
}
else
pairs.put(a[i],1);
}
int count=0;
for (Entry<Integer, Integer> entry : pairs.entrySet()) {
int val=entry.getValue()/2;
count=count+val;
}
System.out.println(count);
}
```