### BUGGY CODE ###

import numpy as np
import sys
 
seg_unit = 0
 
 
def seg_f(x, y):
    return x | y
 
 
def build(seg, raw_data):
    N = len(seg) // 2
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def fold(seg, l, r):
    vl = vr = 0
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)
 
def main(N, S, query):
    seg = np.zeros(N + N, np.int64)
    build(seg, 1 << S)
    for _ in range(query):
        a, b = map(int,input().split())
        a -= 1
        x = fold(seg, a, b)
        print(bin(x).count('1'))

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')
 
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
 
    seg_f = cc_export(seg_f, (i8, i8))
    build = cc_export(build, (i8[:], i8[:]))
    set_val = cc_export(set_val, (i8[:], i8, i8))
    fold = cc_export(fold, (i8[:], i8, i8))
    cc.compile()
 
from my_module import seg_f, build, set_val, fold
 
N, Q = map(int,input().split())
S = np.array(list(map(int,input().split())), np.int64)
 
main(N, S, Q)

### FIXED CODE ###

import sys
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class BIT():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.UNITY_SUM = 0
        self.dat = [[self.UNITY_SUM for i in range(n + 1)] for j in range(2)]
    
    def sub_ADD(self, p, a, x):
        i = a
        while i < len(self.dat[p]):
            self.dat[p][i] = self.dat[p][i] + x
            i += i & -i
    
    def ADD(self, a, b, x):
        self.sub_ADD(0, a, x * -(a - 1))
        self.sub_ADD(1, a, x)
        self.sub_ADD(0, b, x * (b - 1))
        self.sub_ADD(1, b, x * (-1))
    
    def sub_SUM(self, p, a):
        res = self.UNITY_SUM
        i = a
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
    
    def SUM(self, a, b):
        return self.sub_SUM(0, b - 1) + self.sub_SUM(1, b - 1) * (b - 1) - self.sub_SUM(0, a - 1) - self.sub_SUM(1, a - 1) * (a - 1)
    
    def PRINT(self):
        for i in range(1, len(self.dat[0])):
            print(self.SUM(i, i + 1), end = "")
            print(",", end = "")
        print()

def main():
    N, Q = map(int,readline().split())
    C = list(map(int,readline().split()))  #対象のリスト
    S = sys.stdin.readlines()
    lefts = [0] * Q
    rights = [0] * Q
    ids = [0] * Q
    for i in range(Q):
        lefts[i], rights[i] = map(int,S[i].split())
        lefts[i] -= 1
        ids[i] = i
    
    ids = sorted(ids, key=lambda x: rights[x])

    bit = BIT(N+5)
    prev = [-1] * 1100000
    res = [0] * Q
    r = 0
    for i in ids:
        while r < rights[i]:
            bit.ADD(prev[C[r]]+2, r+2, 1)
            prev[C[r]] = r
            r += 1
        tmp = bit.SUM(lefts[i]+1, lefts[i]+2)
        res[i] = max(res[i], tmp)
    for i in range(Q):
        print(res[i])

main()