Buggy python submission (verdict: Time Limit Exceeded):
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 = []
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])


Fixed submission:
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")

Buggy python submission (verdict: Time Limit Exceeded):
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 x in range(q):
    l, r, 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])


Fixed submission:
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")