import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.function.IntFunction;
 
class EqualPairCounter {
 
    int numberOfEqualPairsLinearithmic(int[] a) {
        Arrays.sort(a);
        int res = 0;
        int currPairs = 1;
        IntFunction<Integer> countFn = (cnt) -> cnt > 1 ? (cnt - 1) * cnt / 2 : 0;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == a[i - 1]) {
                currPairs++;
            } else {
                res += countFn.apply(currPairs);
                currPairs = 1;
            }
        }
 
        res += countFn.apply(currPairs);
        return res;
    }
 
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 1, 2, 1, 2, 4, 5, 1, 2, 4, 5, 1, 2 ,5, 6, 7, 7, 8, 2, 1, 2, 4, 5};
        int pairCount = new EqualPairCounter().numberOfEqualPairsLinearithmic(arr);
        System.out.printf("Res: %s", pairCount); // => 49
    }
}