CodeEff/ECCO huggingface dataset:
# Original solution
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s


n, q = map(int, input().split())
c = list(map(int, input().split()))
queries = []
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    queries.append((i, l, r))
queries.sort(key=itemgetter(2))

ans = [0] * q
# last_visit[i] = 色iの最後のindex
last_visit = [-1] * (n + 1)
query_counter = 0
bit = BIT1(n)
for i in range(n):
    if last_visit[c[i]] != -1:
        bit.add(last_visit[c[i]] + 1, -1)

    last_visit[c[i]] = i
    bit.add(i + 1, +1)

    while query_counter < q and queries[query_counter][2] == i:
        idx, l, r = queries[query_counter]
        ans[idx] = bit.sum(r + 1) - bit.sum(l)
        query_counter += 1

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


# Optimized solution
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s


def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    queries = []
    for i in range(q):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        queries.append((i, l, r))
    queries.sort(key=itemgetter(2))

    ans = [0] * q
    # last_visit[i] = 色iの最後のindex
    last_visit = [-1] * (n + 1)
    query_counter = 0
    bit = BIT1(n)
    for i in range(n):
        if last_visit[c[i]] != -1:
            bit.add(last_visit[c[i]] + 1, -1)

        last_visit[c[i]] = i
        bit.add(i + 1, +1)

        while query_counter < q and queries[query_counter][2] == i:
            idx, l, r = queries[query_counter]
            ans[idx] = bit.sum(r + 1) - bit.sum(l)
            query_counter += 1

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


if __name__ == '__main__':
    main()
# Original solution
n, q = list(map(int, input().split()))


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(list(range(self.n - 1))):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.b[r - 1])
            if l & 1:
                s = self.func(s, self.b[l - 1])
                l += 1
            l >>= 1
            r >>= 1
        return s


c = [int(i) for i in input().split()]
seg = SegmentTree([{i} for i in c], lambda x, y: x | y, set())
for _ in range(q):
    l, r = [int(i) for i in input().split()]
    print((len(seg.get_segment(l-1, r))))

# Optimized solution
class BIT:
    def __init__(self, a, func=int.__add__, one=0):
        self.n = len(a)
        self.func = func
        self.one = one
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.func(self.a[i], x)
            i += i & (-i)

    def get(self, i):
        i += 1
        s = self.one
        while i != 0:
            s = self.func(s, self.a[i])
            i -= i & (-i)
        return s


n, q = list(map(int, input().split()))
c = [int(i)-1 for i in input().split()]
que = [[i, [int(i)-1 for i in input().split()], 0] for i in range(q)]
que.sort(key=lambda x: x[1][1])
last = [-1] * n
bit = BIT([0]*(n+100))
j = 0
for i in range(n):
    if last[c[i]] != -1:
        bit.update(last[c[i]], -1)
    bit.update(i, 1)
    last[c[i]] = i
    while j < q and que[j][1][1] == i:
        que[j][2] = bit.get(i) - bit.get(que[j][1][0]-1)
        j += 1
que.sort()
for i in que:
    print((i[-1]))
# Original solution
#A1~Aiまでの和 O(logN)　iが与えられたとき a1~aiまでの和を計算する(O(log n))
def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

#Ai+=x O(logN)　iとxが与えられたとき ai+=x とする (O(log n))
def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

N,Q=list(map(int, input().split()))
C=list(map(int, input().split()))
LRI=[]
for i in range(Q):
  l,r=list(map(int,input().split()))
  LRI.append((r,l,i))

LRI.sort(key=lambda x:x[0])
lastAppend =[-1]*(N+1)
#A1 ... AnのBIT(1-indexed)
BIT=[0]*(N+1)
ANS=[0]*Q
now=1
for r,l,i in LRI:
  while now<=r:
    c=C[now-1]
    #初めてその種類が登場
    if lastAppend[c]==-1:
      BIT_update(BIT,now,1,N)
    #その種類の登場が2回目　
    else:
      BIT_update(BIT,now,1,N)
      BIT_update(BIT,lastAppend[c],-1,N)
    lastAppend[c]=now                
    now+=1
  ANS[i]=BIT_query(BIT,r)-BIT_query(BIT,l-1)

for ans in ANS:
  print(ans)

# Optimized solution
#A1~Aiまでの和 O(logN)　iが与えられたとき a1~aiまでの和を計算する(O(log n))
def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

#Ai+=x O(logN)　iとxが与えられたとき ai+=x とする (O(log n))
def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

def main():
  N, Q = list(map( int, input().split()))
  C = list( map( int, input().split()))
  LRI = []
  for i in range(Q):
    l, r = list(map( int, input().split()))
    LRI.append((r,l, i))
  LRI.sort(key=lambda x:x[0])
  lastAppend = [-1]*(N+1)
  BIT = [0]*(N+1)
  ANS = [0]*Q
  now = 1
  for r, l, i in LRI:
    while now <= r:
      c = C[now-1]
      if lastAppend[c] == -1:
        BIT_update(BIT, now, 1,N)
      else:
        BIT_update(BIT, now, 1,N)
        BIT_update(BIT, lastAppend[c],-1,N)
      lastAppend[c] = now                
      now += 1
    ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()
# Original solution
def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

def main():
  N,Q=list(map( int, input().split()))
  C=list( map( int, input().split()))
  LRI=[]
  for i in range(Q):
    l,r=list(map( int, input().split()))
    LRI.append((r,l,i))
  LRI=sorted(LRI)
  lastAppend=[-1]*(N+1)
  BIT=[0]*(N+1)
  ANS=[0]*Q
  now=1
  for r,l,i in LRI:
    while now <= r:
      c=C[now-1]
      if lastAppend[c]== -1:
        BIT_update(BIT,now,1,N)
      else:
        BIT_update(BIT,now,1,N)
        BIT_update(BIT,lastAppend[c],-1,N)
      lastAppend[c]=now                
      now+=1
    ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()

# Optimized solution
def main():
    N, Q = list(map( int, input().split()))
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = list(map( int, input().split()))
        LRI.append((r,l,i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    print(( "\n".join( map( str, ANS))))
    
if __name__ == '__main__':
    main()
# Original solution
import sys
input = sys.stdin.readline

def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

def main():
  N,Q=list(map( int, input().split()))
  C=list( map( int, input().split()))
  LRI=[]
  for i in range(Q):
    l,r=list(map( int, input().split()))
    LRI.append((r,l,i))
  LRI.sort(key=lambda x:x[0])
  lastAppend=[-1]*(N+1)
  BIT=[0]*(N+1)
  ANS=[0]*Q
  now=1
  for r,l,i in LRI:
    while now <= r:
      c=C[now-1]
      if lastAppend[c]== -1:
        BIT_update(BIT,now,1,N)
      else:
        BIT_update(BIT,now,1,N)
        BIT_update(BIT,lastAppend[c],-1,N)
      lastAppend[c]=now                
      now+=1
    ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()

# Optimized solution
import sys
input = sys.stdin.readline
#A1~Aiまでの和 O(logN)　iが与えられたとき a1~aiまでの和を計算する(O(log n))
def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

#Ai+=x O(logN)　iとxが与えられたとき ai+=x とする (O(log n))
def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

N,Q=list(map(int, input().split()))
C=list(map(int, input().split()))
LRI=[]
for i in range(Q):
  l,r=list(map(int,input().split()))
  LRI.append((r,l,i))

LRI.sort(key=lambda x:x[0])
lastAppend =[-1]*(N+1)
#A1 ... AnのBIT(1-indexed)
BIT=[0]*(N+1)
ANS=[0]*Q
now=1
for r,l,i in LRI:
  while now<=r:
    c=C[now-1]
    #初めてその種類が登場
    if lastAppend[c]==-1:
      BIT_update(BIT,now,1,N)
    #その種類の登場が2回目　
    else:
      BIT_update(BIT,now,1,N)
      BIT_update(BIT,lastAppend[c],-1,N)
    lastAppend[c]=now                
    now+=1
  ANS[i]=BIT_query(BIT,r)-BIT_query(BIT,l-1)

for ans in ANS:
  print(ans)
# Original solution
import sys, math, bisect



if(__name__ == "__main__"):

    N, Q = list(map(int, input().strip().split() ))
    colors = list( map(int, input().strip().split() ) )

    Num_colors_list= [ [0]*N for _ in range(N) ]

    Queries = [ [0, 0] for _ in range(Q) ]
    for i in range(Q):
        l, r = list(map(int, input().strip().split() ))
        Queries[i] = [l, r]

    color = colors[0]-1
    Num_colors_list[0][color] =1

    for i in range(1, N):
        color = colors[i]-1
        for j in range(N):
            Num_colors_list[i][j] =Num_colors_list[i-1][j]
        Num_colors_list[i][color] += 1
    #print(Num_colors_list)
    for q in range(Q):
        N_color_lr = 0
        query = Queries[q]

        if(query[0] == 1):
            for i in range(N):
                if(Num_colors_list[ query[1]-1 ][i]>0):
                    N_color_lr += 1
        else:
            for i in range(N):
                if(Num_colors_list[ query[1]-1 ][i]- Num_colors_list[ query[0]-2 ][i]>0):
                    N_color_lr += 1

        print(N_color_lr)


# Optimized solution
import sys, math, bisect



if(__name__ == "__main__"):

    N, Q = list(map(int, input().strip().split() ))
    colors = list( map(int, input().strip().split() ) )



    Queries = [ [0, 0] for _ in range(Q) ]
    for i in range(Q):
        l, r = list(map(int, input().strip().split() ))
        Queries[i] = [l, r]

    colors_pos = [ [] for _ in range(N) ]

    for i in range(N):
        color = colors[i]-1
        colors_pos[color].append(i)

    for q in range(Q):
        N_color_lr = 0
        query = Queries[q]
        left = query[0] -1
        right = query[1] - 1

        N_types = 0
        if(left==0):
            #rightで考える
            for i in range(N):
                if( bisect.bisect_right(colors_pos[i], right) >0):
                    N_types += 1
        else:
            for i in range(N):
                if( bisect.bisect_right(colors_pos[i], right) - bisect.bisect_left(colors_pos[i], left) >0):
                    N_types += 1
        print(N_types)
# Original solution
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = list(map(int, input().split()))
C = list(map(int, input().split()))

div = max(int(Q**.5), 1)
B = N // div

Qs = []
for i in range(Q):
	l, r = [int(s)-1 for s in input().split()]
	Qs.append((l, r+1, i))

Qs.sort(key=lambda v: (v[0]//B, v[1] ^ -(v[0]//B & 1)))

cnt = [0] * (N+1)
diff = 0

ans = [-1] * Q

left, right = 0, 0

def add(i):
	global cnt, diff
	x = C[i]
	cnt[x] += 1
	if cnt[x] == 1:
		diff += 1

def remove(i):
	global cnt, diff
	x = C[i]
	cnt[x] -= 1
	if cnt[x] == 0:
		diff -= 1

for l, r, i in Qs:
	while right < r:
		add(right)
		right += 1

	while r < right:
		right -= 1
		remove(right)

	while left < l:
		remove(left)
		left += 1

	while l < left:
		left -= 1
		add(left)

	ans[i] = diff

print(('\n'.join(map(str, ans))))


# Optimized solution
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = list(map(int, input().split()))
C = list(map(int, input().split()))

by_R = [[] for _ in range(N+1)]
for i in range(Q):
	l, r = [int(s)-1 for s in input().split()]
	by_R[r+1].append((l, i))

s = [0] * N
def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos-1]
		pos &= pos - 1
	return res

diff = 0
ans = [-1] * Q
last = [-1] * (N+1)

for i, v in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1

	update(i, 1)
	last[v] = i

	for l, j in by_R[i+1]:
		ans[j] = diff - query(l)

print(('\n'.join(map(str, ans))))
# Original solution
x=lambda:list(map(int,input().split()))

def build(s,e,index):
	if s==e:
		seg[index] = {arr[s]}
		return
	mid = (s+e)//2
	build(s,mid,2*index)
	build(mid+1,e,2*index+1)
	seg[index] = set(list(seg[2*index]) + list(seg[2*index+1]))
	return

def query(s,e,qs,qe,index):
	if qe<s or qs>e:
		return set()
	
	if s>=qs and e<=qe:
		return seg[index]
	
	mid = (s+e)//2
	left=query(s,mid,qs,qe,2*index)
	right=query(mid+1,e,qs,qe,2*index+1)
	return set(list(left)+list(right))

n,q = x()
arr = x()
seg=[-1]*(4*n+1)
build(0,n-1,1)
for _ in range(q):
	l,r = x()
	l-=1
	r-=1
	print((len(list(query(0,n-1,l,r,1)))))


# Optimized solution
x=lambda:list(map(int,input().split()))

n,q = x()
arr = x()

for _ in range(q):
	l,r = x()
	l-=1
	print((len(list(set(arr[l:r])))))
# Original solution
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

N, Q = list(map(int, input().split()))
Cs = [0] + list(map(int, input().split()))

Qs = []
for i in range(Q):
  l,r = list(map(int, input().split()))
  Qs.append((i,l,r))
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  st = set()
  for j in range(b,r+1):
    if not Cs[j] in st and Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    st.add(Cs[j])
    dic[Cs[j]] = j
  for s in st:
    bt.add(dic[s], 1)
  ans[i] = bt.get(l-1,r)
  b = r + 1
  
for i in range(Q):
  print((ans[i]))

# Optimized solution
from sys import stdin
input = stdin.readline
class Bit:
    def __init__(self, n):
        self.size = 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.size:
            self.tree[i] += x
            i += i & -i
 
n, q = list(map(int, input().split()))
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = list(map(int, input().split()))
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r+1:
        st = set()
        for j in range(last_update_idx, r+1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r+1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)
# Original solution
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    while i <= self.n:
      self.data[i] += x
      i += i & -i

N, Q = list(map(int, input().split()))
Cs = [0] + list(map(int, input().split()))

Qs = []
for i in range(Q):
  l,r = list(map(int, input().split()))
  Qs.append((i,l,r))
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  if b < r + 1:
    st = set()
    for j in range(b,r+1):
      if not Cs[j] in st and Cs[j] in dic:
        bt.add(dic[Cs[j]],-1)
      st.add(Cs[j])
      dic[Cs[j]] = j
    for s in st:
      bt.add(dic[s], 1)
    b = r + 1
  ans[i] = bt.sum(r) - bt.sum(l-1)
    
for a in ans:
  print(a)

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

N, Q = list(map(int, input().split()))
Cs = [0] + list(map(int, input().split()))

Qs = [None]*Q
for i in range(Q):
  l,r = list(map(int, input().split()))
  Qs[i] = [i,l,r]
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  st = set()
  for j in range(b,r+1):
    if not Cs[j] in st and Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    st.add(Cs[j])
    dic[Cs[j]] = j
  for s in st:
    bt.add(dic[s], 1)
  b = r + 1
  ans[i] = bt.sum(r) - bt.sum(l-1)
    
for a in ans:
  print(a)
# Original solution
from collections import Counter

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))

cs = []

counter = Counter()
for ci in c:
    counter.update([ci])
    c2 = Counter(counter)
    cs.append(c2)

memo = [[-1] * (N+1) for _ in range(N+1)]

for i in range(Q):
    l, r = list(map(int, input().split()))

    if memo[l][r] != -1:
        print((memo[l][r]))
    else:
        c3 = Counter(cs[r-1])
        if l > 1:
            c3.subtract(cs[l-2])
            c3 = +c3
        memo[l][r] = len(c3)
        print((memo[l][r]))


# Optimized solution
import math

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))

M = int(math.sqrt(N))

cs = []
for i in range(0, N, M):
    cs.append(set(c[i:min(i+M, N)]))

for i in range(Q):
    l, r = list(map(int, input().split()))

    li = l // M
    ri = r // M

    if li == ri:
        ans = len(set(c[l-1:r]))
    else:
        s = set(c[l-1:(li+1)*M])
        for j in range(li+1, ri):
            s.update(cs[j])
        s.update(c[ri*M:r])
        ans = len(s)

    print(ans)
# Original solution
import math

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))

M = int(math.sqrt(N))

cs = []
for i in range(0, N, M):
    cs.append(set(c[i:min(i+M, N)]))

for i in range(Q):
    l, r = list(map(int, input().split()))

    li = l // M
    ri = r // M

    if li == ri:
        ans = len(set(c[l-1:r]))
    else:
        s = set(c[l-1:(li+1)*M])
        for j in range(li+1, ri):
            s.update(cs[j])
        s.update(c[ri*M:r])
        ans = len(s)

    print(ans)

# Optimized solution
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n+1)

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

    def add(self, i, x):  # i > 0
        assert i > 0
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))

lr = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    lr.append([l-1, r-1, i])

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

rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]]+1, -1)
    rightest[c[i]] = i
    bit.add(i+1, 1)

    while current_q < Q and lr[current_q][1] == i:
        ans[lr[current_q][2]] = bit.sum(lr[current_q][1] + 1) - bit.sum(lr[current_q][0])
        current_q += 1

for i in range(Q):
    print((ans[i]))
# Original solution
def query(i):
    '''
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    '''
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    
    return res


def update(i, x):
    '''
    a[i-1]にxを加算
    O(logN)
    '''
    while i <= n:
        BIT[i] += x
        i += i & -i


n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
query_ = [list(map(int, input().split())) + [i] for i in range(q)]

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

res = [0] * q
pos = [-1] * n
BIT = [0] * (n+1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i]-1] != -1:
            update(pos[c[i]-1]+1, -1)
        update(i+1, 1)
        pos[c[i]-1] = i
    
    res[idx] = query(r) - query(l-1)
    p = r

for v in res:
    print(v)

# Optimized solution
import sys

input = sys.stdin.readline

def query(i):
    '''
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    '''
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    
    return res


def update(i, x):
    '''
    a[i-1]にxを加算
    O(logN)
    '''
    while i <= n:
        BIT[i] += x
        i += i & -i


n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
query_ = [list(map(int, input().split())) + [i] for i in range(q)]

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

res = [0] * q
pos = [-1] * n
BIT = [0] * (n+1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i]-1] != -1:
            update(pos[c[i]-1]+1, -1)
        update(i+1, 1)
        pos[c[i]-1] = i
    
    res[idx] = query(r) - query(l-1)
    p = r

for v in res:
    print(v)