Submission #57789152

---

Source Code Expand

import sys
import bisect
from collections import deque


def debug(*args):
    print(*args, file=sys.stderr)


n = int(input())
a = list(map(int, input().split()))

appere = [deque([]) for _ in range(n+1)]
count = [0] * (n+1)
for i, ai in enumerate(a):
    appere[ai].append(i)
    count[ai] += 1

ans = 0
ans0 = 0
for i in range(n):
    if i <= appere[a[i]][0]:
        ans0 += 1
    ans += ans0
ans0 = ans
# debug(ans0)
for i in range(1, n):
    if count[a[i-1]] == 1:
        ans0 = ans0 - n + i - 1
    else:
        second_idx = appere[a[i-1]][1]
        ans0 = ans0 - second_idx + i - 1
    # debug(ans0)
    ans += ans0
    count[a[i-1]] -= 1
    appere[a[i-1]].popleft()

print(ans)

Submission Info

Judge Result