Given an array of positive integers of size N. Count the number of good pairs (i,j) such that:
	1≤ i ≤ N,
	1≤ j ≤ N
	and arr_{i} < arr_{j}.
Example 1
Input:
N = 2
arr[] = {2, 1}  
Output: 1
Explanation : The only good pair is (2,1). 
Example 2
Input:
N = 3
arr[] = {2 ,3, 2}
Output: 2
Explanation: The two good pairs are (2,3) 
and (3,2).
Your Task:
You don't need to read input or print anything. Your task is to complete the function solve() which takes the array arr[] and its size N as inputs and returns the count of good pairs as described in the problem description.
Expected Time Complexity: O(N log N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^5
1 <= a[i] <= 10^3

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Complete search

Starter code: #User function Template for python3

class Solution:
    def solve(self, arr : list, n : int):
        # Complete this function

Solutions:
class Solution:

	def binarysearch(self, arr, key, n):
		l = 0
		r = n - 1
		ans = -1
		while l <= r:
			mid = (l + r) // 2
			if arr[mid] > key:
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans

	def solve(self, arr: list, n: int):
		arr.sort()
		count = 0
		for i in arr:
			ans = self.binarysearch(arr, i, n)
			if ans != -1:
				count += n - ans
			else:
				count += 0
		return count


class Solution:

	def solve(self, arr: list, n: int):
		arr.sort()
		res = 0
		for (i, x) in enumerate(arr):
			res += n - bisect(arr, x)
		return res
from bisect import *


class Solution:

	def solve(self, arr: list, n: int):
		arr.sort()
		count = 0
		p = 0
		for i in range(1, n):
			if arr[i - 1] != arr[i]:
				count += i
				p = i
			else:
				count += p
		return count


from collections import Counter

class Solution:

	def solve(self, arr: list, n: int):
		di = Counter(arr)
		di = sorted(di.items(), key=lambda item: item[0])
		count = 0
		su = 0
		for i in range(len(di)):
			su += di[i][1]
			count += (n - su) * di[i][1]
		return count


from collections import Counter

class Solution:

	def solve(self, arr: list, n: int):
		arr.sort()
		count = 0
		prev = 0
		for i in range(1, n):
			if arr[i - 1] != arr[i]:
				count += i
				prev = i
			else:
				count += prev
		return count


class Solution:

	def solve(self, arr: list, n: int):
		arr.sort()
		count = 0
		i = 0
		while i < n:
			curr = 1
			while i + 1 < n and arr[i] == arr[i + 1]:
				i += 1
				curr += 1
			count += curr * (n - 1 - i)
			i += 1
		return count


class Solution:

	def binarysearch(self, arr, l, r, k):
		if l <= r:
			mid = (l + r) // 2
			if arr[mid] > k:
				return self.binarysearch(arr, l, mid - 1, k)
			else:
				return self.binarysearch(arr, mid + 1, r, k)
		return l

	def solve(self, arr: list, n: int):
		arr.sort()
		c = 0
		for i in range(n):
			l = self.binarysearch(arr, 0, n - 1, arr[i])
			c += n - l
		return c


class Solution:

	def solve(self, arr: list, n: int):
		d = {}
		l = []
		for i in range(n - 1, -1, -1):
			if arr[i] in d:
				l.append(d[arr[i]])
				d[arr[i]] += 1
			else:
				l.append(0)
				d[arr[i]] = 1
		l.reverse()
		c = 0
		for i in range(n):
			c += n - 1 - i - l[i]
		return c


class Solution:

	def solve(self, arr: list, n: int):
		if n == 1:
			return 0
		a = sorted(arr)
		d = {}
		c = [a[0]]
		m = 0
		for k in a:
			if k != c[-1]:
				d[c[-1]] = m
				c.append(k)
				m = 1
			else:
				m += 1
		d[c[-1]] = m
		u = 0
		for i in range(1, len(c)):
			u += d[c[i]] * sum([d[c[j]] for j in range(i)])
		return u


class Solution:

	def solve(self, a: list, n: int):
		a.sort()
		ans = n * (n - 1) // 2
		res = 1
		for i in range(n - 1):
			if a[i] == a[i + 1]:
				res += 1
			else:
				ans = ans - res * (res - 1) // 2
				res = 1
		ans = ans - res * (res - 1) // 2
		return ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ob = Solution()
	print(ob.solve(arr, n))


from collections import Counter
from math import factorial

class Solution:

	def solve(self, arr: list, n: int):
		if n == 1:
			return 0
		k = sum([factorial(i) // factorial(i - 2) // factorial(2) for i in dict(Counter(arr)).values() if i >= 2])
		return factorial(n) // factorial(n - 2) // factorial(2) - k


class Solution:

	def solve(self, arr: list, n: int):
		arr.sort(reverse=True)
		count = 1
		res = 0
		for i in range(n - 1):
			if arr[i] == arr[i + 1]:
				count += 1
			else:
				res += count * (n - i - 1)
				count = 1
		return res


import bisect

class Solution:

	def solve(self, arr: list, n: int):
		arr.sort()
		ret = 0
		for i in arr:
			ret += n - bisect.bisect_right(arr, i)
		return ret