Submission #70432642

---

Source Code Expand

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int[] A = new int[N];
        
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        
        long[] leftCount = new long[N + 1];
        long[] rightCount = new long[N + 1];
        
        for (int i = 0; i < N; i++) {
            rightCount[A[i]]++;
        }
        
        long count = 0;
        long pairSum = 0;
        
        for (int j = 0; j < N; j++) {
            pairSum -= leftCount[A[j]] * rightCount[A[j]];
            rightCount[A[j]]--;
            pairSum += leftCount[A[j]] * rightCount[A[j]];
            
            if (j > 0 && j < N - 1) {
                long leftSize = j;
                long rightSize = N - j - 1;
                long leftSame = leftCount[A[j]];
                long rightSame = rightCount[A[j]];
                
                count += leftSame * (rightSize - rightSame);
                count += (leftSize - leftSame) * rightSame;
                count += pairSum - leftSame * rightSame;
            }
            
            pairSum -= leftCount[A[j]] * rightCount[A[j]];
            leftCount[A[j]]++;
            pairSum += leftCount[A[j]] * rightCount[A[j]];
        }
        
        System.out.println(count);
        sc.close();
    }
}

Submission Info

Judge Result