##### Short Problem Definition:

Sherlock is given an array of N integers A0, A1 … AN-1 by Watson. Now Watson asks Sherlock how many different pairs of indices i and j exist such that i is not equal to j but Ai is equal to Aj.

That is, Sherlock has to count total number of pairs of indices (i, j) where Ai = Aj AND i ≠ j.

##### Link

##### Complexity:

time complexity is `O(n)`

space complexity is `O(n)`

##### Execution:

The first step is to create a count of all integers. Next there are choose(k,2)*2 distinct pairs for each integer count (this step similar to Handshake, but you count i,j and j,i as two distinct pairs). Count those together and you arrive at the answer.

##### Solution:

```
#!/usr/bin/py
def cnt_equals(arr):
the_map = {}
final_cnt = 0
for value in arr:
if value not in the_map:
the_map[value] = 1
else:
the_map[value] += 1
for value in the_map.values():
if value != 1:
final_cnt += (value*(value-1))
return final_cnt
if __name__ == '__main__':
t = input()
for _ in xrange(t):
n = input()
arr = map(int, raw_input().split())
print cnt_equals(arr)
```