Buggy python submission (verdict: Time Limit Exceeded):
class BIT:
    def __init__(self, n):
        self.array = [0] * (n + 1)
        self.size = n

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

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()


Fixed submission:
import sys
input = sys.stdin.readline


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

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

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()

Buggy python submission (verdict: Time Limit Exceeded):
class BIT:
    def __init__(self, n):
        self.array = [0] * (n + 1)
        self.size = n

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

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


n, q = map(int, input().split())
*C, = map(lambda x: int(x) - 1, input().split())
P = [0] * n
N = [None] * n
for i in range(n)[::-1]:
    if P[C[i]]:
        N[i] = P[C[i]]
    P[C[i]] = i
F = [0] * n
B = BIT(n)
for i in range(n):
    if F[C[i]] == 0:
        B.add(i, 1)
        F[C[i]] = 1
XY = [tuple(map(int, input().split())) for j in range(q)]
ids = list(range(q))
ids.sort(key=lambda j: XY[j][0])
a = 0
lst = [0] * q
for j in ids:
    x, y = XY[j]
    for i in range(a, x - 1):
        if N[i]:
            B.add(N[i], 1)
    a = x - 1
    lst[j] = B.sum(y) - B.sum(x - 1)
print(*lst, sep="\n")


Fixed submission:
import sys
input = sys.stdin.readline


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

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

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


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

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

    def add(self, i, x):
        self.e[i] += x
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [0] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = sorted([(tuple(map(int, input().split())), j) for j in range(q)])
    a = 0
    lst = [0] * q
    for (x, y), j in XY:
        for i in range(a, x - 1):
            B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()


Fixed submission:
import sys
input = sys.stdin.readline


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

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

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()

Buggy python submission (verdict: Time Limit Exceeded):
class BIT:
    def __init__(self, n):
        self.size = n
        self.array = [0] * (n + 1)
        self.e = [0] * n

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

    def add(self, i, x):
        self.e[i] += x
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


n, q = map(int, input().split())
*C, = map(lambda x: int(x) - 1, input().split())
P = [0] * n
N = [0] * n
for i in range(n)[::-1]:
    if P[C[i]]:
        N[i] = P[C[i]]
    P[C[i]] = i
F = [0] * n
B = BIT(n)
for i in range(n):
    if F[C[i]] == 0:
        B.add(i, 1)
        F[C[i]] = 1
XY = sorted([(tuple(map(int, input().split())), _) for _ in range(q)])
a = 0
lst = []
for (x, y), _ in XY:
    for i in range(a, x - 1):
        B.add(N[i], 1)
    a = x - 1
    lst.append((_, B.sum(y) - B.sum(x - 1)))
lst.sort()
for _, ans in lst:
    print(ans)


Fixed submission:
import sys
input = sys.stdin.readline


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

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

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
*C, = map(int, input().split())
k = 2**19
S = [set()] * (2 * k - 1)
for i in range(n):
    S[k - 1 + i] = {C[i]}
for i in range(k - 1)[::-1]:
    S[i] = S[2 * i + 1] | S[2 * i + 2]
for _ in range(q):
    x, y = map(int, input().split())
    x, y = x + k - 2, y + k - 1
    ans = set()
    while x < y:
        if x % 2 == 0:
            ans |= S[x]
            x += 1
        if y % 2 == 0:
            y -= 1
            ans |= S[y]
        x, y = (x - 1) // 2, (y - 1) // 2
    print(len(ans))


Fixed submission:
import sys
input = sys.stdin.readline


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

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

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
*C, = map(int, input().split())
k = 2**19
S = [set()] * (2 * k - 1)
for i in range(n):
    S[k - 1 + i] = {C[i]}
for i in range(k - 1)[::-1]:
    S[i] = S[2 * i + 1] | S[2 * i + 2]


def ans(a=0, b=k, p=0):
    if b <= x or y <= a:
        return set()
    if x <= a and b <= y:
        return S[p]
    left = ans(a, (a + b) // 2, 2 * p + 1)
    right = ans((a + b) // 2, b, 2 * p + 2)
    return left | right


for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    print(len(ans()))


Fixed submission:
import sys
input = sys.stdin.readline


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

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

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()

Buggy python submission (verdict: Runtime Error):
n, q = map(int, input().split())
*C, = map(int, input().split())
k = 2**16
S = [set()] * (2 * k - 1)
for i in range(n):
    S[k - 1 + i] = {C[i]}
for i in range(k - 1)[::-1]:
    S[i] = S[2 * i + 1] | S[2 * i + 2]


def ans(a=0, b=k, p=0):
    if b <= x or y <= a:
        return set()
    if x <= a and b <= y:
        return S[p]
    left = ans(a, (a + b) // 2, 2 * p + 1)
    right = ans((a + b) // 2, b, 2 * p + 2)
    return left | right


for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    print(len(ans()))


Fixed submission:
import sys
input = sys.stdin.readline


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

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

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()