import sys
from bisect import bisect_left

def main():
    sys.setrecursionlimit(1 << 25)
    N, *rest = map(int, sys.stdin.read().split())
    A = rest[:N]

    from collections import defaultdict
    pos = defaultdict(list)
    for idx, num in enumerate(A):
        pos[num].append(idx + 1)  # 1-based

    total = 0

    for x in pos:
        occurrences = pos[x]
        prefix = [0] * (len(occurrences) + 1)
        ptr = 0
        current_cnt = 0
        transformed = []
        for i in range(1, N + 1):
            if ptr < len(occurrences) and i == occurrences[ptr]:
                current_cnt += 1
                ptr += 1
            t = 2 * current_cnt - i
            transformed.append(t)
        transformed = [0] + transformed  # add t[0] = 0

        # Coordinate compression
        sorted_ts = sorted(set(transformed))
        rank = {v: i+1 for i, v in enumerate(sorted_ts)}  # 1-based indexing for Fenwick

        ft_size = len(sorted_ts)
        ft = [0] * (ft_size + 2)

        def fenwick_update(idx):
            while idx <= ft_size:
                ft[idx] += 1
                idx += idx & -idx

        def fenwick_query(idx):
            res = 0
            while idx > 0:
                res += ft[idx]
                idx -= idx & -idx
            return res

        for t in transformed:
            r = bisect_left(sorted_ts, t)
            cnt = fenwick_query(r)
            total += cnt
            compressed = rank[t]
            fenwick_update(compressed)

    print(total)

if __name__ == '__main__':
    main()