CodeEff/ECCO huggingface dataset:
# Original solution
from operator import itemgetter
n,q=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l2=sorted(l,key=itemgetter(1))

L=[-1]*(5*10**5+1)

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

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l2[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l2[i][2]]=BIT.sum(l2[i][1]+1)-BIT.sum(l2[i][0])

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

# Optimized solution
n,q=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l2=sorted(l,key=lambda x:x[1])

L=[-1]*(5*10**5+1)

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

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l2[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l2[i][2]]=BIT.sum(l2[i][1]+1)-BIT.sum(l2[i][0])

for i in range(q):
  print((ans[i]))
# Original solution
n,q=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l2=sorted(l,key=lambda x:x[1])

L=[-1]*(5*10**5+1)

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

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l2[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l2[i][2]]=BIT.sum(l2[i][1]+1)-BIT.sum(l2[i][0])

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

# Optimized solution
n,q=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l.sort(key=lambda x:x[1])

L=[-1]*(5*10**5+1)

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

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l[i][2]]=BIT.sum(l[i][1]+1)-BIT.sum(l[i][0])

for i in range(q):
  print((ans[i]))
# Original solution
import sys
input=sys.stdin.readline
from operator import itemgetter
n,q=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l.sort(key=lambda x:x[1])

L=[-1]*(5*10**5+1)

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

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l[i][2]]=BIT.sum(l[i][1]+1)-BIT.sum(l[i][0])

for i in ans:
  print(i)

# Optimized solution
import sys
input=sys.stdin.readline
n,q=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[]
for i in range(q):
  L,R=list(map(int,input().split()))
  l.append([L,R,i])
l.sort(key=lambda x:x[1])

L=[-1]*(5*10**5+1)

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

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l[i][2]]=BIT.sum(l[i][1]+1)-BIT.sum(l[i][0])

for i in range(q):
  print((ans[i]))
# Original solution
import sys
input=sys.stdin.readline
n,q=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[]
for i in range(q):
  L,R=list(map(int,input().split()))
  l.append([L,R,i])
l.sort(key=lambda x:x[1])

L=[-1]*(5*10**5+1)

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

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i,j,k in l:
  while ct<=j:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[k]=BIT.sum(j+1)-BIT.sum(i)

for i in ans:
  print(i)

# Optimized solution
import sys
input=sys.stdin.readline
n,q=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[]
for i in range(q):
  L,R=list(map(int,input().split()))
  l.append([L,R,i])
l.sort(key=lambda x:x[1])

L=[-1]*(5*10**5+1)

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

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l[i][2]]=BIT.sum(l[i][1]+1)-BIT.sum(l[i][0])

for i in range(q):
  print((ans[i]))
# Original solution
from dataclasses import dataclass

class BIT:
    '''
    All methods use 0-based index while the implementation use 1-based index
    '''
    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N

    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            i += i & (-i)

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

    def sum_in(self, l, r): # [l, r]
        return self.sum_to(r) - self.sum_to(l - 1)


@dataclass
class Query:
    i: int
    l: int
    r: int


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

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

V = max(C)
bit = BIT(N)
last = [-1] * (max(C) + 1)

query_idx = 0
ans = [-1] * Q
for i, c in enumerate(C):
    if last[c] != -1:
        bit.add_at(last[c], -1)    
    bit.add_at(i, +1)
    last[c] = i

    for q in queries[i]:
        ans[q.i] = bit.sum_in(q.l, q.r)

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

# Optimized solution

class BIT:
    '''
    All methods use 0-based index while the implementation use 1-based index
    '''
    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N
    
    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            i += i & (-i)
    
    def sum_to(self, idx):
        res = 0
        i = idx + 1
        while i > 0:
            res += self.data[i]
            i -= i & (-i)
        return res
    
    def sum_in(self, l, r): # [l, r]
        return self.sum_to(r) - self.sum_to(l - 1)
    
    
class Query:
    def __init__(self, i, l, r):
        self.i = i
        self.l = l
        self.r = r
    
    
N, Q = list(map(int, input().split()))
C = list(map(int, input().split()))
    
queries = [[] for _ in range(N)]
for i in range(Q):
    l, r = list(map(int, input().split()))
    l, r = l - 1, r - 1
    queries[r].append(Query(i, l, r))
    
bit = BIT(N)
last = [-1] * (max(C) + 1)
    
query_idx = 0
ans = [-1] * Q
for i, c in enumerate(C):
    if last[c] != -1:
        bit.add_at(last[c], -1)    
    bit.add_at(i, +1)
    last[c] = i
    
    for q in queries[i]:
        ans[q.i] = bit.sum_in(q.l, q.r)
    
print(('\n'.join(map(str, ans))))
# Original solution
N, Q = list(map(int, input().split()))
Color = [0] + list(map(int, input().split()))
Query =[]
for i in range(Q):
    l, r = list(map(int, input().split()))
    Query.append((r, l, i))
Query.sort()
Ans = [0] * Q

BIT = [0] * (N + 1)  # BITを使う


def BIT_query(idx):  # idxまでの合計を返す
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum


def BIT_update(idx,x):  # idxにxを足す
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return


cn = max(Color)
Last = [-1] * cn

cnt = 0
for r, l, i in Query:
    while cnt < r:
        cnt += 1
        c = Color[cnt] - 1
        if Last[c] == -1:
            Last[c] = cnt
            BIT_update(cnt, 1)
        else:
            x = Last[c]
            BIT_update(x, -1)
            Last[c] = cnt
            BIT_update(cnt, 1)
    Ans[i] = BIT_query(r) - BIT_query(l-1)

for a in Ans:
    print(a)

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

N, Q = list(map(int, input().split()))
Color = [0] + list(map(int, input().split()))
Query =[]
for i in range(Q):
    l, r = list(map(int, input().split()))
    Query.append(r * 10 ** 12 + l * 10 ** 6 + i)
Query.sort()
Ans = [0] * Q

BIT = [0] * (N + 1)  # BITを使う


def BIT_query(idx):  # idxまでの合計を返す
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum


def BIT_update(idx,x):  # idxにxを足す
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return


cn = max(Color)
Last = [-1] * cn

cnt = 0
for q in Query:
    r = q // 10 ** 12
    l = (q % 10 ** 12) // 10 ** 6
    i = q % 10 ** 6
    while cnt < r:
        cnt += 1
        c = Color[cnt] - 1
        if Last[c] == -1:
            Last[c] = cnt
            BIT_update(cnt, 1)
        else:
            x = Last[c]
            BIT_update(x, -1)
            Last[c] = cnt
            BIT_update(cnt, 1)
    Ans[i] = BIT_query(r) - BIT_query(l-1)

for a in Ans:
    print(a)
# Original solution
import sys
input = sys.stdin.readline
from collections import *

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

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

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

lr = [(i,)+tuple(map(int, input().split())) for i in range(Q)]
lr.sort(key=lambda t: t[1], reverse=True)
idx = 0
bit = BIT(N)
ans = []

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    while idx<Q and lr[idx][1]-1==x:
        i, l, r = lr[idx][0], lr[idx][1]-1, lr[idx][2]-1
        ans.append((i, r-l+1-bit.acc(r+1)))
        idx += 1
    
ans.sort(key=lambda t: t[0])

for ans_i in ans:
    print((ans_i[1]))

# Optimized solution
import sys
input = sys.stdin.readline
from collections import *

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

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

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

que = defaultdict(list)

for i in range(Q):
    l, r = list(map(int, input().split()))
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = []

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans.append((i, r-x+1-bit.acc(r+1)))
    
ans.sort(key=lambda t: t[0])

for ans_i in ans:
    print((ans_i[1]))
# Original solution
import sys
input = sys.stdin.readline
from collections import *

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

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

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

que = defaultdict(list)

for i in range(Q):
    l, r = list(map(int, input().split()))
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = []

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans.append((i, r-x+1-bit.acc(r+1)))
    
ans.sort(key=lambda t: t[0])

for ans_i in ans:
    print((ans_i[1]))

# Optimized solution
import sys
input = sys.stdin.readline
from collections import *

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

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

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

que = defaultdict(list)

for i in range(Q):
    l, r = list(map(int, input().split()))
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = [-1]*Q

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans[i] = r-x+1-bit.acc(r+1)

for ans_i in ans:
    print(ans_i)
# Original solution
class BIT:
    # 1-indexed
    def __init__(self, n):
        self.size = n + 1
        self.bit = [0] * self.size

    def add(self, i, x):
        """Add x to a[i]."""
        while i < self.size:
            self.bit[i] += x
            i += i & -i

    def sumup(self, i):
        """Sum a[1]~a[i]."""
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        """Sum a[i]~a[j]."""
        return self.sumup(j) - self.sumup(i - 1)


N, Q = map(int, input().split())
C = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(Q)]

ans = [0] * Q
last_appeared = [0] * (N + 1)
bit = BIT(N + 1)
rm = 0
for i, (l, r) in sorted(enumerate(X), key=lambda x: x[1][1]):
    for j in range(rm + 1, r + 1):
        if last_appeared[C[j - 1]] > 0:
            bit.add(last_appeared[C[j - 1]], -1)
        last_appeared[C[j - 1]] = j
        bit.add(j, 1)

    rm = r
    ans[i] = bit.query(l, r)

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


# Optimized solution

class BIT:
    # 1-indexed
    def __init__(self, n):
        self.size = n + 1
        self.bit = [0] * self.size

    def add(self, i, x):
        # Add x to a[i]
        while i < self.size:
            self.bit[i] += x
            i += i & -i

    def sumup(self, i):
        # Sum a[1]~a[i]
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        # Sum a[i]~a[j]
        return self.sumup(j) - self.sumup(i - 1)


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

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

ans = [0] * Q
bit = BIT(N + 1)
last = [0] * (N + 1)
k = 0
for i, l, r in X:
    for j in range(k + 1, r + 1):
        if last[C[j - 1]] > 0:
            bit.add(last[C[j - 1]], -1)

        bit.add(j, 1)
        last[C[j - 1]] = j

    k = r
    ans[i] = bit.query(l, r)

print(*ans, sep="\n")
# Original solution
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return list(map(int, input().split()))
def read_index(): return [int(x) - 1 for x in input().split()]
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class SegmentTree:
    def __init__(self, S):
        N = len(S)
        d = N.bit_length()
        T = [0 for _ in range(2 ** (d + 1) - 1)]
        for i, s in enumerate(S):
            T[i + 2 ** d - 1] = 1 << s
        for i in range(2 ** d - 2, -1, -1):
            T[i] = T[2 * i + 1] | T[2 * i + 2]
        self.d = d
        self.T = T

    def update(self, i, a):
            i = i + 2 ** self.d - 1
            while i > 0:
                i = (i - 1) // 2
                self.T[i] = self.T[2 * i + 1] | self.T[2 * i + 2]
    
    def query(self, a, b):
        return self._query(a, b, 0, 0, 2 ** self.d)

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0

        if a <= l and r <= b:
            return self.T[k]
        else:
            s1 = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
            s2 = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
            return s1 | s2


def main():
    N, Q = read_values()
    C = read_list()

    ST = SegmentTree(C)
    for _ in range(Q):
        a, b = read_index()
        print((format(ST.query(a, b + 1), "b").count("1")))


if __name__ == "__main__":
    main()



# Optimized solution
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return list(map(int, input().split()))
def read_index(): return [int(x) - 1 for x in input().split()]
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


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

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

    def _sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.T[i]
            i -= i & -i
        return s

    def sum(self, i, j):
        si = self._sum(i - 1)
        sj = self._sum(j)
        return sj - si
    

def main():
    N, M = read_values()
    C = read_list()
    Q = []
    for i in range(M):
        l, r = read_index()
        Q.append((l, r, i))
    Q.sort(key=lambda a: a[1])

    ans = [0] * M
    T = [-1] * M
    bit = BIT(N)
    q = 0
    # print(Q)
    for i in range(N):
        c = C[i] - 1
        t = T[c]
        if t != -1:
            bit.add(t, -1)
        T[c] = i
        bit.add(i, 1)

        # print(i, T, bit.T)
        while q < len(Q) and i == Q[q][1]:
            l, r, k = Q[q]
            ans[k] = bit.sum(l, r)
            q += 1

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

  
if __name__ == "__main__":
    main()
# Original solution
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = list(map(int, input().split()))
color = list(map(int, input().split()))
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 = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)


# 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)