Problem:
 Score : 600 points    Problem Statement We have N colored balls arranged in a row from left to right; the color of the i -th ball from the left is c_i .  You are given Q queries. The i -th query is as follows: how many different colors do the l_i -th through r_i -th balls from the left have?      Constraints  1\leq N,Q \leq 5 \times 10^5  1\leq c_i \leq N  1\leq l_i \leq r_i \leq N  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  Q  c_1  c_2  \cdots  c_N  l_1  r_1  l_2  r_2  :  l_Q  r_Q       Output Print Q lines. The i -th line should contain the response to the i -th query.        Sample Input 1 4 3
1 2 1 3
1 3
2 4
3 3      Sample Output 1 2
3
1   The 1 -st, 2 -nd, and 3 -rd balls from the left have the colors 1 , 2 , and 1 - two different colors.  The 2 -st, 3 -rd, and 4 -th balls from the left have the colors 2 , 1 , and 3 - three different colors.  The 3 -rd ball from the left has the color 1 - just one color.        Sample Input 2 10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8      Sample Output 2 1
2
2
1
2
2
6
3
3
3

Solution (Python):
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 = map(int, input().split())
c = list(map(int, input().split()))
last = [-1]*n
foradd = [[] for i in range(n)]
for i in range(n):
    if last[c[i]-1] != -1: foradd[last[c[i]-1]].append(i)
    last[c[i]-1] = i
forsum = [[] for i in range(n)]
for i in range(q):
    l, r = map(int, input().split()); l -= 1; r -= 1
    forsum[l].append([r, i])
bit = Bit(n); ans = [-1]*q
for i in range(n-1, -1, -1):
    for j in foradd[i]: bit.add(j, 1)
    for j in forsum[i]: ans[j[1]] = j[0]-i+1-bit.sum(j[0])
print(*ans, sep="\n")

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007


class BIT:
    def __init__(self, li):
        self.n, self.data = len(li) + 1, [0] + li
        for i in range(1, self.n):
            if i + (i & -i) < self.n: self.data[i + (i & -i)] += self.data[i]

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

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

    
    def get(self, l, r = None):
        if r is None: r = l+1
        return self.acc(r) - self.acc(l)


def main():
    N, Q = LI()
    C = LI()
    lr = sorted(enumerate(LIR(Q)), key=lambda x: x[1][1])
    rightmostIndex = [-1]*(N+1)
    tree = BIT([0]*N)
    left, right = 0, 0
    ans = [None] * Q

    for i, (l, r) in lr:
        while right < r:
            if rightmostIndex[C[right]] < 0:
                rightmostIndex[C[right]] = right
            else:
                tree.add(rightmostIndex[C[right]], -1)
                rightmostIndex[C[right]] = right
            tree.add(right, 1)
            right += 1

        ans[i] = tree.get(l-1, r)


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


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin

input = stdin.readline
from collections import defaultdict


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

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

    def get_sum(self, ind):
        ind += 1
        res = 0
        while ind > 0:
            res += self.arr[ind]
            ind -= (ind & -ind)
        return res


def solve():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    query = [tuple(map(int, inp.split())) for inp in stdin.read().splitlines()]
    prev = [-1] * (N+1)
    nxt = [-1] * (N+1)
    for i, v in enumerate(c):
        if prev[v] != -1:
            nxt[prev[v]] = i
        prev[v] = i
    q = defaultdict(list)
    for i, (l, r) in enumerate(query):
        q[l - 1].append((r - 1, i))
    bit = BIT(N)
    ans = [0] * Q
    for l in range(N - 1, -1, -1):
        if nxt[l] != -1:
            bit.add(nxt[l], 1)
        for r, i in q[l]:
            ans[i] = r - l + 1 - bit.get_sum(r)
    for a in ans:
        print(a)

if __name__ == '__main__':
    solve()

Solution (Python):
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 map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, 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
    
    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)

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

Solution (Python):
"""
    Satwik_Tiwari ;) .
    12th Sept , 2020  - Saturday
"""



from __future__ import division, print_function


import sys
import os
from io import BytesIO, IOBase























BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

























mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") 
def out(var): sys.stdout.write(str(var))  
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())

def zerolist(n): return [0]*n
def nextline(): out("\n")  
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case 
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     
    x = x % p  
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : 
            res = (res * x) % p

        y = y >> 1      
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True



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

    def sum(self,x):
        sum = 0
        while(x>0):
            sum+=self.tree[x]
            x-=x&(-x)
        return sum

    def update(self,x,k):
        while(x<=self.n):
            self.tree[x]+=k
            x+=x&(-x)

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)

def solve(case):
    n,q = sep()
    c = lis()
    query = []
    for i in range(q):
        l,r = sep()
        query.append((r,l,i))

    query = sorted(query,key=lambda x:x[0])
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind][0] == i+1):
            ans[query[ind][2]] = (bit.sum(i+1) - bit.sum(query[ind][1]-1))
            ind+=1

    print('\n'.join(str(ans[i]) for i in range(len(ans))))

testcase(1)

Solution (Python):
"""
    Satwik_Tiwari ;) .
    12th Sept , 2020  - Saturday
"""



from __future__ import division, print_function


import sys
import os
from io import BytesIO, IOBase























BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

























mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") 
def out(var): sys.stdout.write(str(var))  
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())

def zerolist(n): return [0]*n
def nextline(): out("\n")  
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case 
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     
    x = x % p  
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : 
            res = (res * x) % p

        y = y >> 1      
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True



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

    def sum(self,x):
        sum = 0
        while(x>0):
            sum+=self.tree[x]
            x-=x&(-x)
        return sum

    def update(self,x,k):
        while(x<=self.n):
            self.tree[x]+=k
            x+=x&(-x)

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)

def solve(case):
    n,q = sep()
    c = lis()
    query = []
    for i in range(q):
        l,r = sep()
        query.append((r,l,i))

    query = sorted(query,key=lambda x:x[0])
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind][0] == i+1):
            ans[query[ind][2]] = (bit.sum(i+1) - bit.sum(query[ind][1]-1))
            ind+=1

    print('\n'.join(str(ans[i]) for i in range(len(ans))))

testcase(1)

Solution (Python):
"""
    Satwik_Tiwari ;) .
    12th Sept , 2020  - Saturday
"""



from __future__ import division, print_function


import sys
import os
from io import BytesIO, IOBase























BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

























mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") 
def out(var): sys.stdout.write(str(var))  
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())

def zerolist(n): return [0]*n
def nextline(): out("\n")  
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case 
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     
    x = x % p  
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : 
            res = (res * x) % p

        y = y >> 1      
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True



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

    def sum(self,x):
        sum = 0
        while(x>0):
            sum+=self.tree[x]
            x-=x&(-x)
        return sum

    def update(self,x,k):
        while(x<=self.n):
            self.tree[x]+=k
            x+=x&(-x)

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)

def solve(case):
    n,q = sep()
    c = lis()
    query = []
    for i in range(q):
        l,r = sep()
        query.append((r,l,i))

    query = sorted(query,key=lambda x:x[0])
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind][0] == i+1):
            ans[query[ind][2]] = (bit.sum(i+1) - bit.sum(query[ind][1]-1))
            ind+=1

    print('\n'.join(str(ans[i]) for i in range(len(ans))))

testcase(1)

Solution (Python):
"""
    Satwik_Tiwari ;) .
    12th Sept , 2020  - Saturday
"""



from __future__ import division, print_function


import sys
import os
from io import BytesIO, IOBase























BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

























mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") 
def out(var): sys.stdout.write(str(var))  
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())

def zerolist(n): return [0]*n
def nextline(): out("\n")  
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case 
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     
    x = x % p  
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : 
            res = (res * x) % p

        y = y >> 1      
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True



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

    def sum(self,x):
        sum = 0
        while(x>0):
            sum+=self.tree[x]
            x-=x&(-x)
        return sum

    def update(self,x,k):
        while(x<=self.n):
            self.tree[x]+=k
            x+=x&(-x)

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)
class Query:
    def __init__(self, r,l, idx):
        self.l = l
        self.r = r
        self.idx = idx

def solve(case):
    n,q = sep()
    c = lis()
    query = []
    for i in range(q):
        l,r = sep()
        query.append(Query(r,l,i))

    query = sorted(query,key=lambda x:x.r)
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind].r == i+1):
            ans[query[ind].idx] = (bit.sum(i+1) - bit.sum(query[ind].l-1))
            ind+=1

    print('\n'.join(str(ans[i]) for i in range(len(ans))))

testcase(1)

Solution (Python):
"""
    Satwik_Tiwari ;) .
    12th Sept , 2020  - Saturday
"""



from __future__ import division, print_function


import sys
import os
from io import BytesIO, IOBase























BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

























mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") 
def out(var): sys.stdout.write(str(var))  
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())

def zerolist(n): return [0]*n
def nextline(): out("\n")  
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case 
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     
    x = x % p  
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : 
            res = (res * x) % p

        y = y >> 1      
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True



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

    def sum(self,x):
        sum = 0
        while(x>0):
            sum+=self.tree[x]
            x-=x&(-x)
        return sum

    def update(self,x,k):
        while(x<=self.n):
            self.tree[x]+=k
            x+=x&(-x)

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)
class Query:
    def __init__(self, r,l, idx):
        self.l = l
        self.r = r
        self.idx = idx

def solve(case):
    n,q = sep()
    c = lis()
    query = []
    for i in range(q):
        l,r = sep()
        query.append(Query(r,l,i))

    query.sort(key=lambda x:x.r)
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind].r == i+1):
            ans[query[ind].idx] = (bit.sum(i+1) - bit.sum(query[ind].l-1))
            ind+=1

    print('\n'.join(str(ans[i]) for i in range(len(ans))))

testcase(1)

Solution (Python):
class BIT:
    def __init__(self,n):
        self.n = n
        self.tree = [0]*(n+1)

    def sum(self,x):
        sum = 0
        while(x>0):
            sum+=self.tree[x]
            x-=x&(-x)
        return sum

    def update(self,x,k):
        while(x<=self.n):
            self.tree[x]+=k
            x+=x&(-x)

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)
class Query:
    def __init__(self, r,l, idx):
        self.l = l
        self.r = r
        self.idx = idx

def solve(case):
    n,q = map(int,input().split())
    c = list(map(int,input().split()))
    query = []
    for i in range(q):
        l,r = map(int,input().split())
        query.append(Query(r,l,i))

    query.sort(key = lambda x:x.r)
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind].r == i+1):
            ans[query[ind].idx] = (bit.sum(i+1) - bit.sum(query[ind].l-1))
            ind+=1

    print('\n'.join(str(ans[i]) for i in range(len(ans))))
    
    
solve(1)