CodeEff/ECCO huggingface dataset:
# Original solution
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from bisect import bisect

def resolve():
    it = map(int, sys.stdin.read().split())
    N, Q = next(it), next(it)
    C = [next(it) for i in range(N)]
    D = list(zip(it, it, range(Q)))

    D.sort(key=lambda x: (x[1], x[0]), reverse=True)

    C1 = [[-1, []] for i in range(N)]
    rx = D[0][1]
    for i, ci in zip(range(rx), C):
        x = C1[ci-1]
        x[1].append(x[0])
        x[0] = i
    C2 = C1[:]
    C2.sort()

    ans = [0] * Q
    rj = rx
    for li, ri, i in D:
        if ri < rj:
            for j in reversed(range(ri, rj)):
                cj = C[j] - 1
                x = C1[cj]
                x[0] = x[1].pop()
            C2.sort()
            rj = ri

        k = bisect(C2, [li-1,])
        ans[i] = N - k

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()


# Optimized solution
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = Q.bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & b1

        for j in range(offset, r+1):
            ci = Aa[j]

            lo = N1 + dp[ci]
            hi = N1 + j

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1

            dp[ci] = j + 1
        offset = r+1
        l = Ac[i]

        num = 0
        j = l + N1
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()
# Original solution
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class Segtree():
    def __init__(self, aa):
        self.inf = 0
        self.n = n = len(aa)
        self.tree_width = tree_width = 1 << (n - 1).bit_length()
        self.tree = [-self.inf] * (tree_width * 2 - 1)
        self.tree[tree_width-1:tree_width-1+n]=aa
        for u in range(tree_width - 2, -1, -1):
            self.tree[u] = self.tree[u * 2 + 1]+self.tree[u * 2 + 2]

    def add(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] += a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = self.tree[seg_i * 2 + 1]+self.tree[seg_i * 2 + 2]

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最大値
    def sum(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return 0
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.sum(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.sum(l, r, seg_i * 2 + 2, segM, segR)
        return ret0+ret1

n,q=MI()
cc=LI()
lri=[]
mx=500005
#mx=10
for i in range(q):
    l,r=MI()
    l-=1
    lri.append((l,r,i))

lri.sort(key=lambda x:x[1])

#print(lri)
last=[-1]*mx
st=Segtree([0]*mx)
ans=[0]*q
now=0
for l,r,i in lri:
    for j in range(now,r):
        c=cc[j]
        pre=last[c]
        if pre!=-1:st.add(pre,-1)
        last[c]=j
        st.add(j,1)
    #print(l,r,st.tree,last)
    now=r
    ans[i]=st.sum(l,r)
print(*ans,sep="\n")



# Optimized solution
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class BitSum:
    def __init__(self, n):
        self.n = n + 1
        self.table = [0] * self.n

    def add(self, i, x):
        i += 1
        while i < self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

n,q=MI()
cc=LI()
lri=[]
mx=500005
#mx=10
for i in range(q):
    l,r=MI()
    l-=1
    lri.append((l,r-1,i))

lri.sort(key=lambda x:x[1])

#print(lri)
last=[-1]*mx
st=BitSum(mx)
ans=[0]*q
now=0
for l,r,i in lri:
    for j in range(now,r+1):
        c=cc[j]
        pre=last[c]
        if pre!=-1:st.add(pre,-1)
        last[c]=j
        st.add(j,1)
    #print(l,r,st.tree,last)
    now=r+1
    ans[i]=st.sum(r)-st.sum(l-1)
print(*ans,sep="\n")
# Original solution
import sys
input = sys.stdin.readline

class BIT:

    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)

    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x

    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = list(map(int, input().split()))
    rl[i] = (r, l, i)
rl.sort()
bit = BIT(N+1)
ans = [None] * Q
last_idx = [-1] * (N+1)
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            bit.add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        bit.add(j+1, 1)
        j += 1
    ans[i] = bit.sum(r) - bit.sum(l-1)
for a in ans:
    print(a)
            

# Optimized solution
import sys
input = sys.stdin.readline

def add(x, a):
    while x <= N:
        bit[x] += a
        x += x & -x

def sum(x):
    ret = 0
    while x != 0:
        ret += bit[x]
        x -= x & -x
    return ret

N, Q = map(int, input().split())
bit = [0] * (N+1)
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
ans = [None] * Q
last_idx = [-1] * (N+1)
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        add(j+1, 1)
        j += 1
    ans[i] = sum(r) - sum(l-1)
print(*ans, sep='\n')
# Original solution
import sys
input = sys.stdin.readline

def main():
    N, Q = list(map(int, input().split()))
    bit = [0] * (N+1)

    def add(x, a):
        while x <= N:
            bit[x] += a
            x += x & -x

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    rl = [None] * Q
    for i in range(Q):
        l, r = list(map(int, input().split()))
        rl[i] = (r, l, i)
    rl.sort()
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for r, l, i in rl:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    for a in ans:
        print(a)
            
if __name__ == "__main__":
    main()

# Optimized solution
import sys
input = sys.stdin.readline

def main():
    N, Q = list(map(int, input().split()))
    bit = [0] * (N+1)

    def add(x, a):
        while x <= N:
            bit[x] += a
            x += x & -x

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    lr = [None] * Q
    for i in range(Q):
        l, r = list(map(int, input().split()))
        lr[i] = (i, l, r)
    lr.sort(key=lambda x: x[2])
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for i, l, r in lr:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    for a in ans:
        print(a)
            
if __name__ == "__main__":
    main()
# Original solution
import sys
input = sys.stdin.readline


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n + 2)]
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, q = map(int, input().split())
c = list(map(int, input().split()))

rli = []
for i in range(q):
    l, r = map(int, input().split())
    rli.append((r, l, i))
rli.sort()

last = [-1 for _ in range(n + 1)]

bit = Bit(n)
ans = [-1 for _ in range(q)]
cur = 1
for r, l, i in rli:
    for j in range(cur, r + 1):
        if last[c[j - 1]] != -1:
            bit.add(last[c[j - 1]], -1)
        last[c[j - 1]] = j
        bit.add(j, 1)
    cur = r + 1
    ans[i] = bit.sum(r) - bit.sum(l - 1)
print(*ans, sep="\n")


# Optimized solution
import sys
input = sys.stdin.readline


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n + 2)]
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, q = map(int, input().split())
c = list(map(int, input().split()))

rli = []
for i in range(q):
    l, r = map(int, input().split())
    rli.append((r, l, i))
rli.sort(key=lambda x: x[0])

last = [-1 for _ in range(n + 1)]

bit = Bit(n)
ans = [-1 for _ in range(q)]
cur = 1
for r, l, i in rli:
    for j in range(cur, r + 1):
        if last[c[j - 1]] != -1:
            bit.add(last[c[j - 1]], -1)
        last[c[j - 1]] = j
        bit.add(j, 1)
    cur = r + 1
    ans[i] = bit.sum(r) - bit.sum(l - 1)
print(*ans, sep="\n")
# Original solution
from bisect import *
import sys
input = sys.stdin.readline
n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i
query = []
for i in range(q):
    l, r = list(map(int, input().split()))
    query.append((r, l, i))

query.sort()
appear = [-1]*(n+2)
bit = BIT(n)

right = 0
ans = [None]*(q)
for x in range(q):
    r, l, z = query[x]
    for i in range(right, r):
        if appear[c[i]] != -1:
            bit.add(appear[c[i]]+1, -1)
        appear[c[i]] = i
        bit.add(appear[c[i]]+1, 1)
    right = r
    ans[z] = bit.sum(r) - bit.sum(l-1)

for i in range(q):
    print((ans[i]))


# Optimized solution
from bisect import *
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split()))
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i
query = [list(map(int, input().split()))+[i] for i in range(q)]
query.sort(key = lambda x: x[1])
appear = [-1]*(n+2)
bit = BIT(n)

right = 0
ans = [None]*(q)
for l, r, z in query:
    for i in range(right, r):
        num = appear[c[i]]
        if num != -1:
            bit.add(num+1, -1)
        appear[c[i]] = i
        bit.add(i+1, 1)
    right = r
    ans[z] = bit.sum(r) - bit.sum(l-1)

print(*ans, sep="\n")
# Original solution
class BinaryIndexedTree(object):
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)

    def bit_add(self, index, num):
        while (index <= self.N):
            self.bit[index] += num
            index += index & -index
        return

    def bit_sum(self,index):
        result = 0
        while (index > 0):
            result += self.bit[index]
            index -= index & -index
        return result

    def bit_sum_range(self, l, r):
        if (l == r):
            return 1
        else:
            return self.bit_sum(r) - self.bit_sum(l - 1)

def main():
    from sys import stdin
    N, Q = list(map(int, input().split()))
    c = list(map(int, input().split()))
    readline = stdin.readline
    query = [list(map(int, readline().split())) + [i] for i in range(Q)]
    query_result = [0 for i in range(Q)]
    collar_pos = [-1] * (N + 1)
    bit = BinaryIndexedTree(N)

    sorted_query = sorted(query, key=lambda query: query[1])

    index = 1
    for query in sorted_query:
        while (index <= query[1]):
            # update BIT
            if (collar_pos[c[index-1]] != -1):
                bit.bit_add(collar_pos[c[index-1]], -1)
            bit.bit_add(index, 1)
            # update collar_pos
            collar_pos[c[index-1]] = index
            index += 1
        query_result[query[2]] = bit.bit_sum_range(query[0], query[1])

    print(*query_result, sep='\n')

if __name__ == '__main__':
    main()


# Optimized solution
class BinaryIndexedTree(object):
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)

    def bit_add(self, index, num):
        while (index <= self.N):
            self.bit[index] += num
            index += index & -index
        return

    def bit_sum(self,index):
        result = 0
        while (index > 0):
            result += self.bit[index]
            index -= index & -index
        return result

    def bit_sum_range(self, l, r):
        if (l == r):
            return 1
        else:
            return self.bit_sum(r) - self.bit_sum(l - 1)

def main():
    from sys import stdin
    N, Q = list(map(int, input().split()))
    c = list(map(int, input().split()))
    readline = stdin.readline
    query = [list(map(int, readline().split())) + [i] for i in range(Q)]
    query_result = [0 for i in range(Q)]
    collar_pos = [-1] * (N + 1)
    bit = BinaryIndexedTree(N)

    sorted_query = sorted(query, key=lambda query: query[1])

    index = 1
    for query in sorted_query:
        l, r, q = query
        while (index <= r):
            # update BIT
            if (collar_pos[c[index-1]] != -1):
                bit.bit_add(collar_pos[c[index-1]], -1)
            bit.bit_add(index, 1)
            # update collar_pos
            collar_pos[c[index-1]] = index
            index += 1
        query_result[q] = bit.bit_sum_range(l, r)

    print(*query_result, sep='\n')

if __name__ == '__main__':
    main()
# Original solution
def main():
    n,q=list(map(int,input().split()))
    lst=[0]*n
    clst=tuple(map(int,input().split()))
    work={}
    for i in range(n):
        if clst[i] in work:
            work[clst[i]]+=1
        else :
            work[clst[i]]=1
        lst[i]=work.copy()
    
    for _ in range(q):
        l,r=list(map(int,input().split()))
        rwork=lst[r-1]
        if l==1 :
            print((len(rwork)))
            continue
        lwork=lst[l-2]
        sm=len(rwork)
        for x in rwork:
            if x not in lwork : continue
            if rwork[x]==lwork[x]:
                sm-=1
        print(sm)

main()
        

# Optimized solution
def main():
    n,q=list(map(int,input().split()))
    clst=tuple(map(int,input().split()))
    
    for _ in range(q):
        l,r=list(map(int,input().split()))
        print((len(set(clst[l-1:r]))))

main()
# Original solution
#!/usr/bin/env python3

MAX_VAL = 5 * 10 ** 5 + 1


class FenwickTree(object):
 
    def __init__(self, num_elems):
        self.num_elems = num_elems
        self.data = [0 for _ in range(num_elems)]
 
    def sum_to(self, end):
        s = 0
        i = end - 1
        while i >= 0:
            s += self.data[i]
            i = (i & (i + 1)) - 1
        return s
 
    def sum_range(self, start, end):
        return self.sum_to(end) - self.sum_to(start)
 
    def add(self, idx, x):
        while idx < self.num_elems:
            self.data[idx] += x
            idx |= idx + 1


def answer_queries(n, q, cs, queries):
    ft = FenwickTree(n + 1)
    last_visit = [-1] * MAX_VAL
    sorted_queries = sorted(queries, key=lambda x: x[1])
    ans = [0] * q
    qc = 0
    for i in range(n):
        if last_visit[cs[i]] != -1:
            ft.add(last_visit[cs[i]], -1)
        last_visit[cs[i]] = i
        ft.add(i, 1)
        while qc < q and sorted_queries[qc][1] == i:
            sqqc = sorted_queries[qc]
            ans[sqqc[2]] = ft.sum_range(sqqc[0], sqqc[1] + 1)
            qc += 1
    for i in range(q):
        yield ans[i]


def main():
    n, q = (int(z) for z in input().split())
    cs = [int(c) for c in input().split()]
    queries = []
    for i in range(q):
        le, ri = (int(z) - 1 for z in input().split())
        queries.append((le, ri, i))
    for a in answer_queries(n, q, cs, queries):
        print(a)


if __name__ == '__main__':
    main()

# Optimized solution
#!/usr/bin/env pypy3

MAX_VAL = 5 * 10 ** 5 + 1


class FenwickTree(object):
 
    def __init__(self, num_elems):
        self.num_elems = num_elems
        self.data = [0 for _ in range(num_elems)]
 
    def sum_to(self, end):
        s = 0
        i = end - 1
        while i >= 0:
            s += self.data[i]
            i = (i & (i + 1)) - 1
        return s
 
    def sum_range(self, start, end):
        return self.sum_to(end) - self.sum_to(start)
 
    def add(self, idx, x):
        while idx < self.num_elems:
            self.data[idx] += x
            idx |= idx + 1


def answer_queries(n, q, cs, queries):
    ft = FenwickTree(n + 1)
    last_visit = [-1] * MAX_VAL
    sorted_queries = sorted(queries, key=lambda x: x[1])
    ans = [0] * q
    qc = 0
    for i in range(n):
        if last_visit[cs[i]] != -1:
            ft.add(last_visit[cs[i]], -1)
        last_visit[cs[i]] = i
        ft.add(i, 1)
        while qc < q and sorted_queries[qc][1] == i:
            sqqc = sorted_queries[qc]
            ans[sqqc[2]] = ft.sum_range(sqqc[0], sqqc[1] + 1)
            qc += 1
    for i in range(q):
        yield ans[i]


def main():
    n, q = (int(z) for z in input().split())
    cs = [int(c) for c in input().split()]
    queries = []
    for i in range(q):
        le, ri = (int(z) - 1 for z in input().split())
        queries.append((le, ri, i))
    for a in answer_queries(n, q, cs, queries):
        print(a)


if __name__ == '__main__':
    main()
# Original solution
import sys
input = sys.stdin.readline

N, Q = list(map(int, input().split()))
c = [int(i) for i in input().split()]
lr = [[int(i) for i in input().split()] for _ in range(Q)]

class SegTree:
  def __init__(self, n) :
    i = 1
    while i < n : 
      i <<= 1
    self.n = i
    self.tree = [set() for _ in range((i << 1))]

  def update(self, i, x) :
    i += self.n - 1
    self.tree[i].add(x)
    while i > 0 :
      i = (i - 1) // 2
      self.tree[i] = self.tree[i * 2 + 1] | self.tree[i * 2 + 2]

  # [l, r)
  def query(self, l, r) :
    l = l + self.n
    r = r + self.n
    s = set()
    while l < r :
      if r & 1 :
        r -= 1
        s |= self.tree[r - 1]
      if l & 1 :
        s |= self.tree[l - 1]
        l += 1
      l >>= 1
      r >>= 1
    return len(s)

ST = SegTree(N + 5)
for i in range(N) :
  ST.update(i, c[i])
 
for l, r in lr :
  print((ST.query(l - 1, r)))

# Optimized solution
import sys
input = sys.stdin.readline

N, Q = list(map(int, input().split()))
c = [int(i) for i in input().split()]
lr = [[int(i) - 1 for i in input().split()] for _ in range(Q)]

class BinaryIndexedTree() :
  def __init__(self, n) :
    self.n = n
    self.tree = [0] * (n + 1)
      
  def sum(self, i) :
    s = 0
    while i > 0 :
      s += self.tree[i]
      i -= i & -i
    return s
      
  def add(self, i, x) :
    while i <= self.n :
      self.tree[i] += x
      i += i & -i

BIT = BinaryIndexedTree(N + 5)
sch = [[i, l, r] for i, (l, r) in enumerate(lr)]
sch.sort(key=lambda x: x[2])
ret = [0] * Q
last = [-1] * (N + 1)

cur = 0
for i, l, r in sch :
  while cur <= r :
    BIT.add(cur + 1, 1)
    pos = last[c[cur]]
    if pos != -1 :
      BIT.add(pos + 1, -1)
    last[c[cur]] = cur
    cur += 1
  ret[i] = BIT.sum(r + 1) - BIT.sum(l)
for r in ret :
  print(r)
# Original solution
#Mo
import sys
input = sys.stdin.readline
n,q=list(map(int, input().split()))
*c,=list(map(int, input().split()))
que=[]
for i in range(q):
    li,ri=list(map(int, input().split()))
    que.append((li-1,ri-1,i))

que.sort(key
    =lambda x:(x[0]//1000,x[1]))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for l,r,j in que:
    while rr<r:
        if cnt[c[rr+1]]==0:
            col+=1
        cnt[c[rr+1]]+=1
        rr+=1
    while rr>r:
        if cnt[c[rr]]==1:
            col-=1
        cnt[c[rr]]-=1
        rr-=1
    while ll>l:
        if cnt[c[ll-1]]==0:
            col+=1
        cnt[c[ll-1]]+=1
        ll-=1
    while ll<l:
        if cnt[c[ll]]==1:
            col-=1
        cnt[c[ll]]-=1
        ll+=1
    ans[j]=col+1
print(('\n'.join(map(str,ans[:q]))))


# Optimized solution
import sys
input=sys.stdin.readline
n,q=list(map(int, input().split()))
*c,=list(map(int, input().split()))

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*(n+1)

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)