Sereja has an array a, consisting of n integers a_1, a_2, ..., a_{n}. The boy cannot sit and do nothing, he decided to study an array. Sereja took a piece of paper and wrote out m integers l_1, l_2, ..., l_{m} (1 ≤ l_{i} ≤ n). For each number l_{i} he wants to know how many distinct numbers are staying on the positions l_{i}, l_{i} + 1, ..., n. Formally, he want to find the number of distinct numbers among a_{l}_{i}, a_{l}_{i} + 1, ..., a_{n}.?

Sereja wrote out the necessary array elements but the array was so large and the boy was so pressed for time. Help him, find the answer for the described question for each l_{i}.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5). The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5) — the array elements.

Next m lines contain integers l_1, l_2, ..., l_{m}. The i-th line contains integer l_{i} (1 ≤ l_{i} ≤ n).


-----Output-----

Print m lines — on the i-th line print the answer to the number l_{i}.


-----Examples-----
Input
10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10

Output
6
6
6
6
6
5
4
3
2
1

Difficulty: interview

Starter code:

Solutions:
import sys
n,m=list(map(int,sys.stdin.readline().split()))

A=list(map(int,sys.stdin.readline().split()))

Ans=[1]

E={}
E[A[-1]]=1
for i in range(n-2,-1,-1):
    if(A[i] in E):
        Ans.append(Ans[-1])
    else:
        E[A[i]]=1
        Ans.append(Ans[-1]+1)

Answer=""
for i in range(m):
    x=int(sys.stdin.readline())
    x-=1
    x=n-1-x
    Answer+=str(Ans[x])+"\n"
sys.stdout.write(Answer)


n, m = [int(i) for i in input().split(' ')]
ai = [int(i) for i in input().split(' ')]
li = []
for i in range(m):
    li.append(int(input()))

s = {ai[n - 1]}
lst = [1] * n
for i in range(n - 2, -1, -1):
    s.add(ai[i])
    lst[i] = len(s)

res = [str(lst[i - 1]) for i in li]
print('\n'.join(res))


n, m = map(int, input().split())
a = list(map(int, input().split()))
ans = [0]*m
d = {}
for i in range(n):
    d[a[i]] = i
ans2 = []
a = set(a)
for j in a:
    ans2.append(d[j])
ans2.sort()
ka = [0]*n
c = len(ans2)
for i in range(c):
    ka[ans2[i]] = c-i
i = 0
while i<n and ka[i] == 0:
    i+=1
for j in range(n-2,-1,-1):
    if ka[j] == 0:
        ka[j] = ka[j+1]
for i in range(m):
    b = int(input()) - 1
    ans[i] = ka[b]
for i in ans:
    print(i)

3

def readln(): return tuple(map(int, input().split()))

n, m = readln()
a = readln()
tmp = set()
cnt = [0] * n
for i in range(n - 1, -1, -1):
    tmp.add(a[i])
    cnt[i] = len(tmp)
ans = []
for _ in range(m):
    l, = readln()
    ans.append(str(cnt[l - 1]))
print('\n'.join(ans))


__author__ = 'sm'
#import sys
#fin = open('data.in','r')
#fout = open("data.out",'w')
#sys.stdin = fi:w
# n
#sys.stdout = fout

def readln():
    return list(map(int,input().split()))

n,m = readln()
data = readln()

dp = [0] * n

dp[n-1] = 1
cache = set()
cache.add(data[n-1])

i = n - 2
while i >= 0:
    if  data[i] in cache:
        dp[i] = dp[i+1]
    else:
        dp[i] = dp[i+1] + 1
        cache.add(data[i])
    i -= 1

ans = []
for  i in range(m):
    idx = readln()[0]
    ans.append(str(dp[idx-1]))

print('\n'.join(ans))



n,m=map(int,input().split())
a=list(map(int,input().split()))
s=set([])
p=[0]*n
for i in reversed(range(n)):
    if not a[i] in s:
        s.add(a[i])
    p[i]=len(s)
for i in range(m):
    l=int(input())
    print(p[l-1])

n,m = map(int,input().split())
a = list (map(int,input().split()))
s = set([])
ans = [0]*n
for i in reversed(range(n)):
	if (not a[i] in s): s.add(a[i])
	ans[i] = len(s)
for i in range(m):
	z = int(input())
	print (ans[z-1])

import sys

def __starting_point():

    n, m = [int(i) for i in sys.stdin.readline().rstrip().split(' ')]
    a = [int(i) for i in sys.stdin.readline().rstrip().split(' ')]
    l = [None] * m
    for i in range(m):
        l[i] = int(sys.stdin.readline().rstrip())

    l_sorted = sorted(l)
    l_order = sorted(range(m), key=lambda k: l[k])

    # the ranks of elements in l
    l_rank = sorted(range(m), key=lambda k: l_order[k])

    # unique_elem[i] = non-duplicated elements between l_sorted[i] and l_sorted[i+1]
    unique_elem = [None] * m

    for i in range(m):
        unique_elem[i] = set(a[(l_sorted[i] - 1): (l_sorted[i + 1] - 1)]) if i < m - 1 else set(a[(l_sorted[i] - 1): n])

    # unique_elem_cumulative[i] = non-duplicated elements between l_sorted[i] and a's end
    unique_elem_cumulative = unique_elem[-1]

    # unique_elem_cumulative_count[i] = #unique_elem_cumulative[i]
    unique_elem_cumulative_count = [None] * m
    unique_elem_cumulative_count[-1] = len(unique_elem[-1])

    for i in range(m - 1):
        i_rev = m - i - 2
        unique_elem_cumulative |= unique_elem[i_rev]
        unique_elem_cumulative_count[i_rev] = len(unique_elem_cumulative)

    for i in range(m):
        idx = l_rank[i]
        print(unique_elem_cumulative_count[idx])
__starting_point()


def main(stdin):
    n, m = next(stdin).split()
    n, m = int(n), int(m)
    a_i = next(stdin).split()
    checked = {}
    diff = {}

    checked[int(a_i[-1])] = 1
    diff[n-1] = 1
    for i in range(n-2, -1, -1):
        diff[i] = diff[i+1]
        if int(a_i[i]) not in checked:
            diff[i] += 1
            checked[int(a_i[i])] = 1

    for l in stdin:
        print(diff[int(l)-1])




def __starting_point():
    import sys
    main(sys.stdin)

__starting_point()

M = lambda: map(int, input().split())
L = lambda: list(map(int, input().split()))
I = lambda: int(input())

n, k = M()
t = reversed(L())
p, r = [0] * (n + 2), [1] * 100001
for i, j in enumerate(t, 1): p[i], r[j] = p[i - 1] + r[j], 0
p.reverse()
print('\n'.join(map(str, (p[I()] for i in range(k)))))

__author__ = 'asmn'
n, m = tuple(map(int, input().split()))
a = list(map(int, input().split()))

s = set()
ans = [0] * n
for i in reversed(range(n)):
    s.add(a[i])
    ans[i] = len(s)

for i in range(m):
    print(ans[int(input()) - 1])

n, m = list(map(int, input().split(' ')))

a = list(map(int, input().split(' ')))
nums = set()
for i in range(n - 1, -1, -1):
    nums.add(a[i])
    a[i] = len(nums)

while m:
    print(a[int(input()) - 1])
    m -= 1


# -*- coding: utf-8 -*-

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

ans = [0] * n
s = set()
for i in range(n-1, -1, -1):
    s.add(a[i])
    ans[i] = len(s)
    
for i in range(m):
    print(ans[l[i]-1])


import sys
input = lambda: sys.stdin.readline()
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
mark = set()
ans = []
for i in range(n-1, -1, -1):
	mark.add(a[i])
	ans.append(len(mark))
for i in range(m):
	print(ans[n-int(input())])


import sys
input = lambda: sys.stdin.readline()
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
mark = [0] * 100001
ans = [0] * 100001
for i in range(n-1, -1, -1):
	ans[i] = ans[i+1] + 1 - mark[a[i]]
	mark[a[i]] = 1
for i in range(m):
	print(ans[int(input())-1])


n, m=map(int, input().split(' '))
array=input().split(' ')
listx=[int(input()) for inpt in range(m)]

nums=set()
for i in range(n-1, -1, -1):
    nums.add(array[i])
    array[i]=len(nums)

for a in range(m):
    print(array[listx[a]-1])

n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
s = [0] * (10**5 + 1)
ans = [0] * n
for i in range(n):
	if not s[a[n - 1 - i]]:
		s[a[n - 1 - i]] = 1
		ans[n - 1 - i] = 1
for i in range(n - 1):
	ans[n - 2 - i] += ans[n - 1 - i]
res = []
for i in range(m):
	res.append(str(ans[int(input()) - 1]))
print('\n'.join(res))


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    c = [0] * n
    c[n - 1] = 1
    s = [False] * 100001
    s[a[n - 1]] = True
    for i in range(1, n):
        if s[a[n - i - 1]]:
            c[n - i - 1] = c[n - i]
        else:
            c[n - i - 1] = c[n - i] + 1
            s[a[n - i - 1]] = True
    print('\n'.join(str(c[int(input()) - 1]) for _ in range(m)))


def __starting_point():
    main()
__starting_point()

def main():
    n, m = map(int, input().split())
    aa = list(map(int, input().split()))
    cnt = [True] * 100001
    res = []
    x = 0
    for a in reversed(aa):
        if cnt[a]:
            cnt[a] = False
            x += 1
        res.append(x)
    print('\n'.join(str(res[n - int(input())]) for _ in range(m)))


def __starting_point():
    main()
__starting_point()

def main():
    n, m = map(int, input().split())
    aa = list(map(int, input().split()))
    cnt = [True] * (max(aa) + 1)
    res, x = [], 0
    for a in reversed(aa):
        if cnt[a]:
            cnt[a] = False
            x += 1
        res.append(x)
    print('\n'.join(str(res[n - int(input())]) for _ in range(m)))


def __starting_point():
    main()
__starting_point()

import sys
import math

n,  m = [int(x) for x in (sys.stdin.readline()).split()]
an = [int(x) for x in (sys.stdin.readline()).split()]

k = [0] * n
kj = [0] * 100001

k[n - 1] = 1
kj[an[n - 1]] = 1
for i in range(n - 2, -1,  -1):
    
    z = 0
    if(kj[an[i]] == 0):
        z = 1
    kj[an[i]] = 1    
    k[i] = k[i + 1] + z
    
for i in range(m):
    d = int(sys.stdin.readline())
    print(k[d - 1])

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

sequence = list(map(int, input().split()))
l_list = [int(input()) - 1 for _ in range(m)]


max_num = max(sequence)

f = [0] * (max_num + 1)


k = 0
d = [0] * len(sequence)
for i in range(len(sequence) - 1, -1, -1):
    index = sequence[i]
    if f[index] == 0:
        f[index] = 1
        k += 1
    d[i] = k

for i in l_list:
    print(d[i])