Buggy python submission (verdict: Time Limit Exceeded):
MAX = 1000001


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Time Limit Exceeded):
MAX = 1000001


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    print(*ans)

    # Driver Code


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Time Limit Exceeded):
MAX = 1000001


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    print("\n".join(map(str, ans)))

    # Driver Code


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Time Limit Exceeded):
MAX = 1000001


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])

    # Driver Code


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Runtime Error):
# python3 implementation of above approach
import sys
from math import ceil, log, floor

# Each segment of the segment tree would be a set 
# to maintain distinct elements 
segment = [[] for i in range(10000)]

sys.setrecursionlimit(10 ** 8)


# Build the segment tree
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr):
    # If start is equal to end then
    # append the array element 
    if (s == e):
        segment[i].append(arr[s])
        return

    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


# Query in an range a to b
def query(node, l, r, a, b):
    left, right, result = [], [], []

    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r):
        return result

        # If the range lies in this segment
    if (a <= l and r <= b):
        return segment[node]

    # Else query for the right and left
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)

    # Return the result 
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


# Initialize the segment tree
def init(n):
    # Get the height of the segment tree
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


# Function to get the result for the
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n):
    # Query for the range set
    ans = query(1, 0, n - 1, l, r)

    print(answer(str(ans)))


# Driver code
N, Q = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

# Bulid the segment tree 
build(1, 0, n - 1, C)

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Runtime Error):
# python3 implementation of above approach
import sys
from math import ceil, log, floor

# Each segment of the segment tree would be a set 
# to maintain distinct elements 
segment = [[] for i in range(1000000)]

sys.setrecursionlimit(10 ** 8)


# Build the segment tree
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr):
    # If start is equal to end then
    # append the array element 
    if (s == e):
        segment[i].append(arr[s])
        return

    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


# Query in an range a to b
def query(node, l, r, a, b):
    left, right, result = [], [], []

    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r):
        return result

        # If the range lies in this segment
    if (a <= l and r <= b):
        return segment[node]

    # Else query for the right and left
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)

    # Return the result 
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


# Initialize the segment tree
def init(n):
    # Get the height of the segment tree
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


# Function to get the result for the
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n):
    # Query for the range set
    ans = query(1, 0, n - 1, l, r)

    print(answer(str(ans)))


# Driver code
N, Q = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

# Bulid the segment tree 
build(1, 0, n - 1, C)

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Runtime Error):
# python3 implementation of above approach 
from math import ceil, log, floor

# Each segment of the segment tree would be a set 
# to maintain distinct elements 
segment = [[] for i in range(1000000)]


# Build the segment tree
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr):
    # If start is equal to end then
    # append the array element 
    if (s == e):
        segment[i].append(arr[s])
        return

    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


# Query in an range a to b
def query(node, l, r, a, b):
    left, right, result = [], [], []

    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r):
        return result

        # If the range lies in this segment
    if (a <= l and r <= b):
        return segment[node]

    # Else query for the right and left
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)

    # Return the result 
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


# Initialize the segment tree
def init(n):
    # Get the height of the segment tree
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


# Function to get the result for the
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n):
    # Query for the range set
    ans = query(1, 0, n - 1, l, r)

    print(answer(str(ans)))


# Driver code
N, Q = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

# Bulid the segment tree 
build(1, 0, n - 1, C)

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Runtime Error):
# python3 implementation of above approach 
from math import ceil, log, floor

# Each segment of the segment tree would be a set 
# to maintain distinct elements 
segment = [[] for i in range(100000)]


# Build the segment tree
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr):
    # If start is equal to end then
    # append the array element 
    if (s == e):
        segment[i].append(arr[s])
        return

    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


# Query in an range a to b
def query(node, l, r, a, b):
    left, right, result = [], [], []

    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r):
        return result

        # If the range lies in this segment
    if (a <= l and r <= b):
        return segment[node]

    # Else query for the right and left
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)

    # Return the result 
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


# Initialize the segment tree
def init(n):
    # Get the height of the segment tree
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


# Function to get the result for the
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n):
    # Query for the range set
    ans = query(1, 0, n - 1, l, r)

    print(answer(str(ans)))


# Driver code
N, Q = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

# Bulid the segment tree 
build(1, 0, n - 1, C)

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Runtime Error):
# python3 implementation of above approach 
from math import ceil, log, floor

# Each segment of the segment tree would be a set 
# to maintain distinct elements 
segment = [[] for i in range(10010)]


# Build the segment tree
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr):
    # If start is equal to end then
    # append the array element 
    if (s == e):
        segment[i].append(arr[s])
        return

    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


# Query in an range a to b
def query(node, l, r, a, b):
    left, right, result = [], [], []

    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r):
        return result

        # If the range lies in this segment
    if (a <= l and r <= b):
        return segment[node]

    # Else query for the right and left
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)

    # Return the result 
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


# Initialize the segment tree
def init(n):
    # Get the height of the segment tree
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


# Function to get the result for the
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n):
    # Query for the range set
    ans = query(1, 0, n - 1, l, r)

    print(answer(str(ans)))


# Driver code
N, Q = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

# Bulid the segment tree 
build(1, 0, n - 1, C)

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Runtime Error):
# python3 implementation of above approach 
from math import ceil, log, floor

# Each segment of the segment tree would be a set 
# to maintain distinct elements 
segment = [[] for i in range(1000)]


# Build the segment tree
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr):
    # If start is equal to end then
    # append the array element 
    if (s == e):
        segment[i].append(arr[s])
        return

    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


# Query in an range a to b
def query(node, l, r, a, b):
    left, right, result = [], [], []

    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r):
        return result

        # If the range lies in this segment
    if (a <= l and r <= b):
        return segment[node]

    # Else query for the right and left
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)

    # Return the result 
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


# Initialize the segment tree
def init(n):
    # Get the height of the segment tree
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


# Function to get the result for the
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n):
    # Query for the range set
    ans = query(1, 0, n - 1, l, r)

    print(answer(str(ans)))


# Driver code
N, Q = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

# Bulid the segment tree 
build(1, 0, n - 1, C)

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Runtime Error):
# python3 implementation of above approach 
from math import ceil, log, floor

# Each segment of the segment tree would be a set 
# to maintain distinct elements 
segment = [[] for i in range(1000)]


# Build the segment tree
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr):
    # If start is equal to end then
    # append the array element 
    if (s == e):
        segment[i].append(arr[s])
        return

    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


# Query in an range a to b
def query(node, l, r, a, b):
    left, right, result = [], [], []

    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r):
        return result

        # If the range lies in this segment
    if (a <= l and r <= b):
        return segment[node]

    # Else query for the right and left
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)

    # Return the result 
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


# Initialize the segment tree
def init(n):
    # Get the height of the segment tree
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


# Function to get the result for the
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n):
    # Query for the range set
    ans = query(1, 0, n - 1, l, r)

    print(answer(str(ans)))


# Driver code
N, Q = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

# Bulid the segment tree 
build(1, 0, n - 1, C)

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Runtime Error):
# python3 implementation of above approach 
from math import ceil, log, floor

# Each segment of the segment tree would be a set 
# to maintain distinct elements 
segment = [[] for i in range(1000)]


# Build the segment tree
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr):
    # If start is equal to end then
    # append the array element 
    if (s == e):
        segment[i].append(arr[s])
        return

    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


# Query in an range a to b
def query(node, l, r, a, b):
    left, right, result = [], [], []

    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r):
        return result

        # If the range lies in this segment
    if (a <= l and r <= b):
        return segment[node]

        # Else query for the right and left
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)

    # Return the result 
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


# Initialize the segment tree
def init(n):
    # Get the height of the segment tree
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


# Function to get the result for the
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n):
    # Query for the range set
    ans = query(1, 0, n - 1, l, r)

    print(answer(str(ans)))


# Driver code
N, Q = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
LR = [[int(x) for x in input().split()] for _ in range(Q)]

n = N

init(n)

# Bulid the segment tree 
build(1, 0, n - 1, C)

# Query in range 0 to 4
for l, r in LR:
    getDistinct(l - 1, r - 1, n)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Runtime Error):
# python3 implementation of above approach 
from math import ceil, log, floor

# Each segment of the segment tree would be a set 
# to maintain distinct elements 
segment = [[] for i in range(1000)]


# Build the segment tree
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr):
    # If start is equal to end then
    # append the array element 
    if (s == e):
        segment[i].append(arr[s])
        return

    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


# Query in an range a to b
def query(node, l, r, a, b):
    left, right, result = [], [], []

    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r):
        return result

        # If the range lies in this segment
    if (a <= l and r <= b):
        return segment[node]

        # Else query for the right and left
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)

    # Return the result 
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


# Initialize the segment tree
def init(n):
    # Get the height of the segment tree
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


# Function to get the result for the
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n):
    # Query for the range set
    ans = query(1, 0, n - 1, l, r)

    print(answer(str(ans)))


# Driver code
N, Q = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
LR = [[int(x) for x in input().split()] for _ in range(Q)]

n = N

init(n)

# Bulid the segment tree 
build(1, 0, n - 1, C)

# Query in range 0 to 4
for l, r in LR:
    getDistinct(l - 1, r - 1, n)


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, Q = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    LR = [[int(x) for x in input().split()] for _ in range(Q)]

    def segfunc(x, y):
        # 求めたい値を算出するためのロジックを書く
        return x | y

    def init(init_val):
        for i in range(n):
            seg[i + num - 1].add(init_val[i])

        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return set()
        p += num - 1
        q += num - 2
        res = set()
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # seg tree初期値 (単位元)
    n = N
    # ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    # seg = [ide_ele] * 2 * num
    seg = [set() for j in range(2 * num)]

    init(C)
    for l, r in LR:
        print(len(query(l - 1, r)))


if __name__ == '__main__':
    main()


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, Q = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    LR = [[int(x) for x in input().split()] for _ in range(Q)]

    def segfunc(x, y):
        # 求めたい値を算出するためのロジックを書く
        return x | y

    def init(init_val):
        for i in range(n):
            seg[i + num - 1].add(init_val[i])

        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return set()
        p += num - 1
        q += num - 2
        res = set()
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # seg tree初期値 (単位元)
    n = N
    # ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    # seg = [ide_ele] * 2 * num
    seg = [set() for j in range(2 * num)]

    init(C)
    for l, r in LR:
        print(len(query(l - 1, r)))


if __name__ == '__main__':
    main()


Fixed submission:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

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

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)