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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = [r, l, i]
    query.sort()
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    for i in range(n):
        bit.add(i+1, 1)
        if already[c[i]]:
            bit.subtract(already[c[i]], 1)
        already[c[i]] = i+1
        while index < q:
            key = query[index]
            if key[0] == i+1:
                ans[key[2]] = bit.get_sum(key[1]-1, key[0])
                index += 1
            else:
                break

    for a in ans:
        print(a)

    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = [r, l, i]
    query.sort()
    
    bit = BIT(n)
    index = 0
    already = dict()
    ans = [0]*q
    for i in range(n):
        bit.add(i+1, 1)
        if c[i] in already:
            bit.subtract(already[c[i]], 1)
        already[c[i]] = i+1
        while index < q:
            key = query[index]
            if key[0] == i+1:
                ans[key[2]] = bit.get_sum(key[1]-1, key[0])
                index += 1
            else:
                break

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = [r, l, i]
    query.sort()
    
    bit = BIT(n)
    index = 0
    already = dict()
    ans = [0]*q
    for i in range(n):
        bit.add(i+1, 1)
        if c[i] in already:
            bit.subtract(already[c[i]], 1)
        already[c[i]] = i+1
        while index < q:
            key = query[index]
            if key[0] == i+1:
                ans[key[2]] = bit.get_sum(key[1]-1, key[0])
                index += 1
            else:
                break

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [(r, l, i) for i, (l, r) in enumerate([[int(x) for x in input().split()] for _ in range(q)])]
    query.sort()
    bit = BIT(n)
    ans = [0]*q
    index = 0
    count = 0
    for i in range(n):
        if key[i] != -1:
            count += 1
            bit.add(key[i]+1, 1)
        while True:
            if index == q:
                break
            r, l, c = query[index]
            if r == i+1:
                ans[c] = r-l+1-count+bit.summarize(l-1)
                index += 1
            else:
                break
        if index == q:
            break

    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()




Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    bit = BIT(n)
    ans = [0]*q
    index = 0
    count = 0
    for i in range(n):
        if key[i] != -1:
            count += 1
            bit.add(key[i]+1, 1)
        while True:
            if index == q:
                break
            r, l, c = query[index]
            if r == i:
                ans[c] = r-l+1-count+bit.summarize(l)
                index += 1
            else:
                break
        if index == q:
            break
    
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()




Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    bit = BIT(n)
    ans = [0]*q
    index = 0
    for i in range(n):
        bit.add(i+1, 1)
        if key[i] != -1:
            bit.add(key[i]+1, -1)
        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i:
                ans[query[index][2]] = bit.get_sum(l, r+1)
                index += 1
            else:
                break
        if index == q:
            break
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()



Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    bit = BIT(n)
    ans = [0]*q
    index = 0
    for i in range(n):
        bit.add(i+1, 1)
        if key[i] != -1:
            bit.add(key[i]+1, -1)
        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i:
                ans[query[index][2]] = bit.get_sum(l, r+1)
                index += 1
            else:
                break
        if index == q:
            break
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()



Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    bit = BIT(n)
    ans = [0]*n
    index = 0
    for i in range(n):
        bit.add(i+1, 1)
        if key[i] != -1:
            bit.add(key[i]+1, -1)
        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i:
                ans[query[index][2]] = bit.get_sum(l, r+1)
                index += 1
            else:
                break
        if index == q:
            break
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()



Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    bit = BIT(n)
    ans = [0]*n
    index = 0
    for i in range(n):
        bit.add(i+1, 1)
        if key[i] != -1:
            bit.add(key[i]+1, -1)
        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i:
                ans[query[index][2]] = bit.get_sum(l, r+1)
                index += 1
            else:
                break
        if index == q:
            break
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()



Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

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


class Segment_tree():
    def __init__(self, n):
        self.inf = pow(2, 32)
        self.n = n
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [0]*(self.size)
        for i in range(self.N-1, -1, -1):
            self.segment[i] = self.segment[2*i+1]+self.segment[2*i+2]
        
    def undate(self, i, x):
        i += (self.N)
        self.segment[i] = x
        while i > 0:
            i = (i-1)//2
            self.segment[i] = self.segment[2*i+1]+self.segment[2*i+2]
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return find_l+find_r
    
    def count(self, l, r):
        return self.find(l, r, 0, 0, self.size-self.N)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    segment = Segment_tree(n)
    ans = [0]*q
    index = 0
    for i in range(n):
        segment.undate(i, 1)
        if key[i] != -1:
            segment.undate(key[i], 0)
        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i:
                ans[query[index][2]] = segment.count(l, r+1)
                index += 1
            else:
                break
        if index == q:
            break
    
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()



Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

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

def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    key = [-1]*n
    judge = dict()
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r, l, i)
    
    query.sort()
    
    ans = [None]*q
    index = 0
    judge = []
    for i in range(n):
        if index == q:
            break
        if key[i] != -1:
            bisect.insort(judge, key[i])

        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i+1:
                ans[query[index][2]] = r-l+1-len(judge)+bisect.bisect_left(judge, l-1)
                index += 1
            else:
                break
    for v in ans:
        print(v)
        
    
    
    
    
if __name__ == "__main__":
    main()

Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

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

def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    key = [-1]*n
    judge = dict()
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r, l, i)
    
    query.sort()
    
    ans = [None]*q
    index = 0
    judge = []
    for i in range(n):
        if index == q:
            break
        if key[i] != -1:
            bisect.insort(judge, key[i])

        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i+1:
                ans[query[index][2]] = r-l+1-len(judge)+bisect.bisect_left(judge, l-1)
                index += 1
            else:
                break
    for v in ans:
        print(v)
        
    
    
    
    
if __name__ == "__main__":
    main()

Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

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

class Segment_tree():
    def __init__(self, n, arrange):
        self.inf = pow(2, 32)
        self.n = n
        self.arrange = arrange
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [set()]*(self.N) + self.arrange + [set()]*(self.size-self.N-self.n)
        #この次の処理は、求められる動作に応じて変化させる。ここでは区間最小値問題のコードを書く。
        for i in range(self.N-1, -1, -1):
            self.segment[i] = self.segment[2*i+1]|self.segment[2*i+2]
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set()
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return find_l|find_r
    
    def count(self, l, r):
        return self.find(l, r, 0, 0, self.size-self.N)



def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    key = [None]*n
    
    judge = dict()
    for i in range(n-1, -1, -1):
        if c[i] in judge:
            key[i] = {judge[c[i]]}
        else:
            key[i] = set()
        judge[c[i]] = i
    """
    key2 = [None]*n
    
    judge2 = dict()
    for i in range(n):
        if c[i] in judge2:
            key2[i] = {judge2[c[i]]}
        else:
            key2[i] = set()
        judge2[c[i]] = i
     """   
    segment = Segment_tree(n, key)
    for i in range(q):
        l, r = map(int, input().split())
        judgement = sorted(list(segment.count(l-1, r-1)))
        print(r-l+1-bisect.bisect_left(judgement, r))
    
    
    
    
if __name__ == "__main__":
    main()



Fixed submission:
import sys
from operator import itemgetter
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()