Vlad likes to eat in cafes very much. During his life, he has visited cafes n times. Unfortunately, Vlad started to feel that his last visits are not any different from each other. To fix that Vlad had a small research.

First of all, Vlad assigned individual indices to all cafes. Then, he wrote down indices of cafes he visited in a row, in order of visiting them. Now, Vlad wants to find such a cafe that his last visit to that cafe was before his last visits to every other cafe. In other words, he wants to find such a cafe that he hasn't been there for as long as possible. Help Vlad to find that cafe.


-----Input-----

In first line there is one integer n (1 ≤ n ≤ 2·10^5) — number of cafes indices written by Vlad.

In second line, n numbers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 2·10^5) are written — indices of cafes in order of being visited by Vlad. Vlad could visit some cafes more than once. Note that in numeration, some indices could be omitted.


-----Output-----

Print one integer — index of the cafe that Vlad hasn't visited for as long as possible.


-----Examples-----
Input
5
1 3 2 1 2

Output
3

Input
6
2 1 2 2 4 1

Output
2



-----Note-----

In first test, there are three cafes, and the last visits to cafes with indices 1 and 2 were after the last visit to cafe with index 3; so this cafe is the answer. 

In second test case, there are also three cafes, but with indices 1, 2 and 4. Cafes with indices 1 and 4 were visited after the last visit of cafe with index 2, so the answer is 2. Note that Vlad could omit some numbers while numerating the cafes.

Difficulty: interview

Starter code:

Solutions:
import itertools
import re
import math
import getpass
import sys

debug = False
files = False
if getpass.getuser() == 'frohe':
    debug = True

if debug and files:
    sys.stdin = open('test.in')


def ria():
    return [int(i) for i in input().split()]


n = ria()[0]
ar = ria()
mp = {}
for i in ar:
    mp[i] = 0
for n, i in enumerate(ar):
    mp[i] = n
mini = ar[0]
for i in mp:
    if mp[mini]>mp[i]:
        mini=i
print(mini)

n = int(input())
data = list(map(int, input().split()))
was = {}

for i in range(n):
    was[data[i]] = i

print(min(list(was.keys()), key=was.get))


n = int(input())
a = set()
res = 0
for i in list(map(int, input().split()))[::-1]:
    if i not in a:
        a.add(i)
        res = i
print(res)


def main():
    read = lambda: tuple(map(int, input().split()))
    n = read()[0]
    l = read()
    last = {}
    for i in range(n):
        last[l[i]] = i
    mn = 1e10
    ans = -1
    for k in last:
        if last[k] < mn:
            ans = k
            mn = last[k]
    print(ans)
main()


n = int(input())
arr = list(map(int, input().split()))
was = [10000000000000000000] * (2 * 10 ** 5 + 10)
for i in range(n):
    was[arr[i]] = i
mn = 10 ** 9
mn_i = -1
for el in arr:
    if was[el] < mn:
        mn = was[el]
        mn_i = el
print(mn_i)

q=int(input())
a=list(map(int,input().split()))
s={}
for i in range(0,q):
    s[a[i]]=i
d=min(s.values())
for i in s:
    if s[i]==d:
        print(i)


n = int(input())
a = list(map(int, input().split()))
l = [-1 for i in range(2*10**5 + 10)]

for i in range(n):
    l[a[i]] = i

min_pos = 3 * 10 ** 5
min_s = -1

for i in range(2 * 10 ** 5 + 5):
    if l[i] == -1:
        pass
    else:
        if l[i] < min_pos:
            min_pos = l[i]
            min_s = i

print(min_s)




n = int(input())
a = list(map(int, input().split()))
times = [10 ** 9] * 10 ** 6
for i in range(n):
    times[a[i]] = i
print(times.index(min(times)))

n = int(input())
a = [int(i) for i in input().split()]
b = {}
for i in range(n):
    b[a[i]] = i
b = sorted(b.items(), key=lambda x:x[1])
print(b[0][0])

n = int(input())

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

s = dict()
for i, e in enumerate(mas):
    s[e] = i

print(mas[min(s.values())])

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

c = dict()
for i in range(n):
    a = A[i]
    c[a] = i
mini = 100000000000000
numb = 0
for i in c:
    if c[i] < mini:
        numb = i
        mini = c[i]
print(numb)

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

b = set()
i = a.__len__() - 1
c = 0

while i >= 0:
    if not(a[i] in b):
        c = a[i]
        b.add(a[i])
    i -= 1
print(c)


n = int(input())
a = list(map(int, input().split(' ')))
d = {}

for i in range(n):
    d[a[i]] = i

min = n
min_k = -1

for k in d:
    if d[k] < min:
        min = d[k]
        min_k = k

print(min_k)

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

s = set()
last = 0

for i in range(len(a) - 1, -1, -1):
    if not a[i] in s:
        last = a[i]
        s.add(a[i])

print(last)

n = int(input())
food = list(map(int, input().split()))
times = {}
for i in range(n):
    times[food[i]] = i
t = min(times.values())
print(food[t])


n = int(input())
numbers = list(map(int, input().split()))
last = dict()
for i in set(numbers):
    last[i] = 0

for i in range(n):
    last[numbers[i]] = i

print(min(list(last.items()), key=lambda x: x[1])[0])


import sys
input()
t=list(map(int,input().split()))
s=[2000000 for i in range(200001)]
for i in range(len(t)):
    s[t[i]]=i
mins=2000001
mn=0
for i in range(len(s)):
    if s[i]<mins:
        mins=s[i]
        mn=i
print(mn)


n = int(input())
l = list(map(int, input().split()))
s = set()
ans = -1
for i in range(n - 1, -1, -1):
    if l[i] not in s:
        s.add(l[i])
        ans = l[i]
print(ans)


n = int(input())
mas = list(map(int, input().split()))
dict1 = dict()
for i in range(len(mas)):
    dict1[mas[i]] = i
min_dict1 = dict1[mas[0]]
min_ans = mas[0]
for i in dict1:
    if dict1[i] < min_dict1:
        min_dict1 = dict1[i]
        min_ans = i
print(min_ans)

def ma():
    n=int(input())
    b=list(map(int,input().split()))
    k={b[-1]};last=b[-1]
    for i in range(n-1,-1,-1):
        if not (b[i] in k):
            last=b[i];
            k.add(b[i])
    print(last)
ma()

n = int(input())
a = reversed([int(x) for x in input().split()])
ans = -1
used = [False] * (2 * 10 ** 5 + 13)
for elem in a:
    if not used[elem]:
        used[elem] = True
        ans = elem
print(ans)

n = int(input())
num = list(map(int, input().split()))
used = [False] * 200001
for i in range(len(num) - 1, -1, -1):
    if not used[num[i]]:
        used[num[i]] = True
        ans = num[i]
print(ans)

n = int(input())
s = [200001] * (200001)
a = list(map(int,input().split()))
for i in range(1, n + 1):
    s[a[i-1]] = i - 1
ans = s.index(min(s))
print(ans)

n = int(input())
a = list(map(int,input().split()))
b = set(a)
for i in range(n-1,-1,-1):
    b.discard(a[i])
    if not b:
        print(a[i])
        break


m = {}
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    m[a[i]] = i

ans = 0
k = 1e6
for i in set(a):
    if m[i] < k:
        k = m[i]
        ans = i
print(ans)