Frequenct prefix and suffix

import java.util.*;

public class Main {

    static final int MOD = 1000000007;

    static class Fenwick {
        long[] tree;
        int n;

        Fenwick(int n) {
            this.n = n;
            tree = new long[n + 1];
        }

        void update(int i, long val) {
            while (i <= n) {
                tree[i] += val;
                i += i & -i;
            }
        }

        long query(int i) {
            long sum = 0;
            while (i > 0) {
                sum += tree[i];
                i -= i & -i;
            }
            return sum;
        }
    }

    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[] prefFreq = new long[n];
        long[] prefDistinct = new long[n];

        Map<Integer, Integer> map = new HashMap<>();
        int distinct = 0;

        for (int i = 0; i < n; i++) {
            map.put(A[i], map.getOrDefault(A[i], 0) + 1);
            if (map.get(A[i]) == 1) distinct++;

            prefFreq[i] = map.get(A[i]);
            prefDistinct[i] = distinct;
        }

        long[] suffFreq = new long[n];
        long[] suffDistinct = new long[n];

        map.clear();
        distinct = 0;

        for (int i = n - 1; i >= 0; i--) {
            map.put(A[i], map.getOrDefault(A[i], 0) + 1);
            if (map.get(A[i]) == 1) distinct++;

            suffFreq[i] = map.get(A[i]);
            suffDistinct[i] = distinct;
        }

        long[] L = new long[n];
        long[] R = new long[n];

        for (int i = 0; i < n; i++) {
            L[i] = prefFreq[i] - prefDistinct[i] / 2;
            R[i] = suffDistinct[i] / 2 - suffFreq[i];
        }

        // Coordinate compression
        List<Long> all = new ArrayList<>();
        for (long x : L) all.add(x);
        for (long x : R) all.add(x);

        Collections.sort(all);
        Map<Long, Integer> compress = new HashMap<>();
        int idx = 1;
        for (long x : all)
            if (!compress.containsKey(x))
                compress.put(x, idx++);

        Fenwick bit = new Fenwick(idx + 2);

        long answer = 0;

        for (int j = 1; j < n; j++) {
            bit.update(compress.get(L[j - 1]), 1);
            answer = (answer + bit.query(compress.get(R[j]))) % MOD;
        }

        System.out.println(answer);
    }
}