Since Sonya is interested in robotics too, she decided to construct robots that will read and recognize numbers.

Sonya has drawn $n$ numbers in a row, $a_i$ is located in the $i$-th position. She also has put a robot at each end of the row (to the left of the first number and to the right of the last number). Sonya will give a number to each robot (they can be either same or different) and run them. When a robot is running, it is moving toward to another robot, reading numbers in the row. When a robot is reading a number that is equal to the number that was given to that robot, it will turn off and stay in the same position.

Sonya does not want robots to break, so she will give such numbers that robots will stop before they meet. That is, the girl wants them to stop at different positions so that the first robot is to the left of the second one.

For example, if the numbers $[1, 5, 4, 1, 3]$ are written, and Sonya gives the number $1$ to the first robot and the number $4$ to the second one, the first robot will stop in the $1$-st position while the second one in the $3$-rd position. In that case, robots will not meet each other. As a result, robots will not be broken. But if Sonya gives the number $4$ to the first robot and the number $5$ to the second one, they will meet since the first robot will stop in the $3$-rd position while the second one is in the $2$-nd position.

Sonya understands that it does not make sense to give a number that is not written in the row because a robot will not find this number and will meet the other robot.

Sonya is now interested in finding the number of different pairs that she can give to robots so that they will not meet. In other words, she wants to know the number of pairs ($p$, $q$), where she will give $p$ to the first robot and $q$ to the second one. Pairs ($p_i$, $q_i$) and ($p_j$, $q_j$) are different if $p_i\neq p_j$ or $q_i\neq q_j$.

Unfortunately, Sonya is busy fixing robots that broke after a failed launch. That is why she is asking you to find the number of pairs that she can give to robots so that they will not meet.


-----Input-----

The first line contains a single integer $n$ ($1\leq n\leq 10^5$) — the number of numbers in a row.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\leq a_i\leq 10^5$) — the numbers in a row.


-----Output-----

Print one number — the number of possible pairs that Sonya can give to robots so that they will not meet.


-----Examples-----
Input
5
1 5 4 1 3

Output
9

Input
7
1 2 1 1 1 3 2

Output
7



-----Note-----

In the first example, Sonya can give pairs ($1$, $1$), ($1$, $3$), ($1$, $4$), ($1$, $5$), ($4$, $1$), ($4$, $3$), ($5$, $1$), ($5$, $3$), and ($5$, $4$).

In the second example, Sonya can give pairs ($1$, $1$), ($1$, $2$), ($1$, $3$), ($2$, $1$), ($2$, $2$), ($2$, $3$), and ($3$, $2$).

Difficulty: interview

Starter code:

Solutions:
def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())

n = ii()
a = li()
ans = 0
cnt = [0] * (10 ** 5 + 10)
cur = set()
for ai in a:
    cnt[ai] = len(cur)
    cur.add(ai)
ans = sum(cnt)
print(ans)

def main():
    #string     input()
    #strList    input().split()
    n = int(input())
    #integers   map(int, input().split())
    a = list(map(int, input().split()))
    uniques = [0] * (n - 1) + [1]
    bools = [True] * 100001
    bools2 = [True] * 100001
    bools[a[-1]] = False
    for i in range(n - 2, 0, -1):
        temp = 0
        if bools[a[i]]:
            bools[a[i]] = False
            temp = 1
        uniques[i] = uniques[i + 1] + temp
    ret = 0
    for i in range(n - 1):
        if bools2[a[i]]:
            bools2[a[i]] = False
            ret += uniques[i + 1]
    print(ret)
    return 0
main()


n = int(input())
a = [int(x) for x in input().strip().split()]

f = dict()
b = dict()
for i in range(len(a)):
    if a[i] not in f:
        f[a[i]] = i
    if a[n-1-i] not in b:
        b[a[n-1-i]] = n-1-i

f = sorted([v, k] for k, v in list(f.items()))
b = sorted([v, k] for k, v in list(b.items()))

ans = 0
bi = 0
for i, v in f:
    while bi < len(b) and i >= b[bi][0]:
        bi += 1
    ans += len(b) - bi

print(ans)


n = int(input())
a = [int(x) for x in input().split()]

MAX_NUM = 100010
met_forw = [False] * MAX_NUM
met_backw = [False] * MAX_NUM
unique_n_backw = [0] * n

for i in range(n - 1, -1, -1):
    if i < n - 1:
        unique_n_backw[i] = unique_n_backw[i + 1]
    if not met_backw[a[i]]:
        met_backw[a[i]] = True
        unique_n_backw[i] += 1

answer = 0
for i in range(n - 1):
    if not met_forw[a[i]]:
        met_forw[a[i]] = True
        answer += unique_n_backw[i + 1]

print(answer)


n = int(input())
l = [int(el) for el in input().split()]
col = 0
a = [0] * 100001
s = set()
for i in range(n):
    if a[l[i]] == 0:
        col += len(s)
        a[l[i]] += len(s)
        s.add(l[i])
    else:
        col += len(s) - a[l[i]]
        a[l[i]] = len(s)
        s.add(l[i])
print(col)


n=int(input())
a=list(map(int,input().split()))
b=set()
c=[]
s=0
for i in a:
	if not i in b:
		s+=1
		b.add(i)
	c.append(s)
b=set()
ans=0
for i in range(n-1,0,-1):
	if not a[i] in b:
		ans+=c[i-1]
		b.add(a[i])
print(ans)

import sys
import os

def extract(a):
    d = dict()
    r = []
    for e in a:
        if not e in d:
            r.append(1)
            d[e] = d
        else:
            r.append(0)

    return r

def sonyaAndRobots(n, a):
    t1 = extract(a)
    t2 = list(reversed(extract(reversed(a))))

    for i in range(n - 1):
        t1[i + 1] += t1[i]

    result = 0
    for i in range(n - 1):
        result += t1[i] * t2[i + 1]

    return result

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    print(sonyaAndRobots(n, a))

def __starting_point():
    main()
__starting_point()

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

right = list()
s = set()

for el in a[::-1]:
    s.add(el)
    right.append(len(s))

right = right[::-1]

s = set()
ans = 0

for i, el in enumerate(a[:-1]):
    if el not in s:
        ans += right[i + 1]

    s.add(el)

print(ans)


n=int(input())
arr=list(map(int,input().split()))
dic={}
dic2={}
ansar=[]
for i in range(n):
	dic[arr[i]]=0
	dic2[arr[i]]=0
	ansar.append(0)
count=0
for i in range(n-1,0,-1):
	if dic[arr[i]]==0:
		count+=1
		
		dic[arr[i]]=1
	ansar[i-1]=count	
#print(ansar)
answer=0
for i in range(n-1):
	if dic2[arr[i]]==0:
		answer+=ansar[i]
		dic2[arr[i]]=1
print(answer)	

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

dic = {}
for i in range(len(a) - 1):
    if a[i] not in dic:
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1

been = set([])
cnt = 0
for i in range(len(a) - 1, 0, -1):
    if a[i] not in been:
        cnt += len(dic)
        been.add(a[i])
    dic[a[i - 1]] -= 1
    if (dic[a[i - 1]] == 0):
        del dic[a[i - 1]]
print(cnt)


n=int(input())
a=list(map(int,input().split()))
b=a[:]
s=set()
for i in range(n):
    if(a[i] in s):
        a[i]=0
    else:
        s.add(a[i])
s=set()
c=[0]*n
c[n-1]=1
for i in range(n-1,-1,-1):
    if(b[i] in s):
        b[i]=0
        c[i]=c[i+1]
    else:
        s.add(b[i])
        if(i<n-1):
            c[i]=c[i+1]+1
ans=0
for i in range(n-1):
    if(a[i]):
        ans+=c[i+1]
print(ans)

n = int(input())
a = [int(x) for x in input().split()]
s = set()
d = dict()
c = [0] * n
for i in range(n-1, -1, -1):
    c[i] = len(s)
    s.add(a[i])
    d[a[i]] = i
ans = 0
for k in list(d.keys()):
    pos = d[k]
    ans += c[pos]
print(ans)



from collections import defaultdict
n = int(input())
arr = list(map(int,input().split()))
list1 = [False]*(10**5+1)
d = defaultdict(int)
count = 0 
for i in range(n):
	d[arr[i]] += 1
for i in range(n-1):
	d[arr[i]] -= 1
	if(d[arr[i]] == 0):
		del(d[arr[i]])
	if list1[arr[i]] == False:
		count += len(list(d.items()))
		list1[arr[i]] = True


print(count)


from collections import defaultdict

n = int(input())

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

counts = defaultdict(int)

for x in a:
    counts[x] += 1

keys = set()
c = len(counts)
ans = 0

for x in a[:-1]:
    if x not in keys:
        keys.add(x)
        counts[x] -= 1
        if counts[x] == 0:
            c -= 1
        ans += c
    else:
        counts[x] -= 1
        if counts[x] == 0:
            c -= 1
print(ans)



def main():
	n = int(input())
	a = tuple(map(int, input().split()))
	seen = set()
	count = 0
	distinct = [0]
	for x in reversed(a):
		if x in seen:
			distinct.append(distinct[-1])
			continue
		seen.add(x)
		distinct.append(distinct[-1]+1)
	distinct.pop()
	seen.clear()
	#print(tuple(reversed(distinct)))
	for x, distinct_right in zip(a, reversed(distinct)):
		#print(x, distinct_right)
		if x in seen:
			continue
		seen.add(x)
		count += distinct_right

	print(count)
main()

n = int(input())
A = list(map(int, input().split()))
left = [0 for _ in range(10**5 + 1)]
right = [0 for _ in range(10**5 + 1)]
r_non0 = 0
for a in A:
    if right[a] == 0:
        r_non0 += 1
    right[a] += 1
ans = 0
for i in range(n):
    left[A[i]] += 1
    right[A[i]] -= 1
    if right[A[i]] == 0:
        r_non0 -= 1
    if left[A[i]] == 1:
        ans += r_non0
print(ans)

n = int(input())
positions = input().split()
s1 = set()
l1 = [1] * (n - 1)
s2 = set()
l2 = []
count = 0
for i in range(n - 1):
    if positions[i] in s1:l1[i] = 0
    s1.add(positions[i])
for i in range(n - 1):
    s2.add(positions[-1 - i])
    l2.append(len(s2))
for i in range(n - 1):
    count+=l1[i] * l2[-1 - i]
print(count)

from collections import defaultdict

n = int(input())
a = [int(i) for i in input().split()]

done = set()
d = defaultdict(int)

for i in a:
    d[i] += 1

c = len(list(d.keys()))
total = 0
for i in (a):
    d[i] -= 1
    if d[i] == 0:
        c -= 1

    if i not in done:
        total += c
        done.add(i)


print(total)




n = int(input())
a = input().split(" ")
for i in range(n):
    a[i] = int(a[i])
lu = {}
for i in range(n):
    lu[a[i]] = []
for i in range(n):
    lu[a[i]].append(i)
mins = []
maxes = []
for val in lu.values():
    mins.append(min(val))
    maxes.append(max(val))
key_num = len(lu.keys())
mins.sort()
maxes.sort()
# print(mins)
# print(maxes)
ind = 0
pairs = 0
counter = key_num
for i in range(len(mins)):
    while maxes[ind] <= mins[i]:
        if ind == len(maxes) - 1:
            counter = 0
            break
        else:
            ind += 1
            counter -= 1
    pairs += counter
    # print(counter)
print(pairs)

n=int(input())
l=list(map(int,input().split()))
maxl=max(l)+1
dp=[]
for i in range(maxl):
    dp.append([-1,-1])
for i in range(n):
    dp[l[i]][1]=i
for i in range(n-1,-1,-1):
    dp[l[i]][0]=i
ll=[]
lr=[]
for i in range(n):
    ll.append(0)
    lr.append(0)
cnt = 0
for i in range(maxl):
    if(dp[i][0]!=-1):
        ll[dp[i][0]]=1
        lr[dp[i][1]]=1
        cnt+=1
ans = 0

for i in range(n):
    if(lr[i]==1):
        cnt-=1
    if(ll[i]==1):
        ans+=cnt
print(ans)

n = int(input())
A = list(map(int, input().split()))
res_set = set()
tmp_set = set()
NumList = [0 for i in range(n)]
for i in range(n - 1, -1, -1):
    tmp_set.add(A[i])
    NumList[i] = len(tmp_set)
ans = 0
for i in range(n - 1):
    if not (A[i] in res_set):
        res_set.add(A[i])
        ans += NumList[i + 1]
#print(NumList)
#print(res_set)
print(ans)


n=int(input())
s=list(map(int,input().split()))
dist=[]
p=[0 for i in range(100005)]
diff=0
for i in range(n-1,-1,-1):
    if p[s[i]]==0:
        p[s[i]]=1
        diff+=1
    else:
        p[s[i]]+=1
    dist+=[diff]
vis=[0 for i in range(100005)]
ans=0
for i in range(n-1):
    if vis[s[i]]==0:
        ans+=dist[n-i-2]
        vis[s[i]]=1
print(ans)

n=int(input())
nums = list(map(int, input().split()))
left = {}

for i in range(n):
    if nums[i] in list(left.keys()):
        left[nums[i]] += 1
    else:
        left[nums[i]] = 1

count = 0
done = set()
for i in nums:
    left[i] -= 1
    if left[i] == 0:
        del left[i]
    if i not in done:
        count += len(list(left.keys()))
        done.add(i)

print(count)


n = int(input())
a = list(map(int, input().split()))
d = {}
for i in range(n):
    if d.get(a[i]) == None:
        d[a[i]] = 1
    else:
        d[a[i]] += 1
count = 0
used = set()
for i in range(n):
    d[a[i]] -= 1
    if d[a[i]] == 0:
        del d[a[i]]
    if a[i] not in used:
        count += len(d)
    used.add(a[i])
print(count)