Buggy python submission (verdict: Time Limit Exceeded):
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,1)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+sum_(l)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()


Fixed submission:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]
class BIT:
    def __init__(self, size):
        self.size = size + 1
        self.dat = [0]*self.size

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

    # sum[l,r)
    # sum[0,l] (r = None)
    def sum(self, l, r=None):
        if r is None:
            res = 0
            while l > 0:
                res += self.dat[l]
                l -= l&-l
            return res

        else:
            rres = 0
            while r > 0:
                rres += self.dat[r]
                r -= r&-r

            l -= 1
            lres = 0
            while l > 0:
                lres += self.dat[l]
                l -= l&-l

            return rres - lres


def solve():
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = BIT(n+1)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                bit.add(j)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+bit.sum(l)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,-1)
            else:
                s += 1
            add(i,1)
            p[ci] = i
            i += 1
        ans[ind] = s-sum_(l-1)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()


Fixed submission:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]
class BIT:
    def __init__(self, size):
        self.size = size + 1
        self.dat = [0]*self.size

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

    # sum[l,r)
    # sum[0,l] (r = None)
    def sum(self, l, r=None):
        if r is None:
            res = 0
            while l > 0:
                res += self.dat[l]
                l -= l&-l
            return res

        else:
            rres = 0
            while r > 0:
                rres += self.dat[r]
                r -= r&-r

            l -= 1
            lres = 0
            while l > 0:
                lres += self.dat[l]
                l -= l&-l

            return rres - lres


def solve():
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = BIT(n+1)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                bit.add(j)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+bit.sum(l)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    for ind,(l, r) in q:
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,-1)
            add(i,1)
            p[ci] = i
            i += 1
        ans[ind] = sum_(r)-sum_(l-1)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()


Fixed submission:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]
class BIT:
    def __init__(self, size):
        self.size = size + 1
        self.dat = [0]*self.size

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

    # sum[l,r)
    # sum[0,l] (r = None)
    def sum(self, l, r=None):
        if r is None:
            res = 0
            while l > 0:
                res += self.dat[l]
                l -= l&-l
            return res

        else:
            rres = 0
            while r > 0:
                rres += self.dat[r]
                r -= r&-r

            l -= 1
            lres = 0
            while l > 0:
                lres += self.dat[l]
                l -= l&-l

            return rres - lres


def solve():
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = BIT(n+1)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                bit.add(j)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+bit.sum(l)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():

    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 0
    p = [None]*(n+1)
    ans = [0]*Q
    for ind,(l, r) in q:
        while i < r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,-1)
            add(i+1,1)
            p[ci] = i+1
            i += 1
        ans[ind] = sum_(r)-sum_(l-1)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()


Fixed submission:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]
class BIT:
    def __init__(self, size):
        self.size = size + 1
        self.dat = [0]*self.size

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

    # sum[l,r)
    # sum[0,l] (r = None)
    def sum(self, l, r=None):
        if r is None:
            res = 0
            while l > 0:
                res += self.dat[l]
                l -= l&-l
            return res

        else:
            rres = 0
            while r > 0:
                rres += self.dat[r]
                r -= r&-r

            l -= 1
            lres = 0
            while l > 0:
                lres += self.dat[l]
                l -= l&-l

            return rres - lres


def solve():
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = BIT(n+1)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                bit.add(j)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+bit.sum(l)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    class SegmentTree:
        def __init__(self, size, f=lambda x,y : x+y, default=0):
            self.size = 2**(size-1).bit_length()
            self.default = default
            self.dat = [default]*(self.size*2)
            self.f = f

        def update(self, i, x):
            i += self.size
            self.dat[i] = x
            while i > 0:
                i >>= 1
                self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

        def get(self, a, b=None):
            if b is None:
                b = a + 1
            l, r = a + self.size, b + self.size
            lres, rres = self.default, self.default
            while l < r:
                if l & 1:
                    lres = self.f(lres, self.dat[l])
                    l += 1

                if r & 1:
                    r -= 1
                    rres = self.f(self.dat[r], rres)
                l >>= 1
                r >>= 1
            res = self.f(lres, rres)
            return res
    n,Q = LI()
    c = LI()
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    s = SegmentTree(n)
    i = 0
    p = [None]*(n+1)
    ans = [0]*Q
    for ind,(l, r) in q:
        l -= 1
        while i < r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                s.update(j,0)
            s.update(i,1)
            p[ci] = i
            i += 1
        ans[ind] = s.get(l,r)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()


Fixed submission:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]
class BIT:
    def __init__(self, size):
        self.size = size + 1
        self.dat = [0]*self.size

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

    # sum[l,r)
    # sum[0,l] (r = None)
    def sum(self, l, r=None):
        if r is None:
            res = 0
            while l > 0:
                res += self.dat[l]
                l -= l&-l
            return res

        else:
            rres = 0
            while r > 0:
                rres += self.dat[r]
                r -= r&-r

            l -= 1
            lres = 0
            while l > 0:
                lres += self.dat[l]
                l -= l&-l

            return rres - lres


def solve():
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = BIT(n+1)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                bit.add(j)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+bit.sum(l)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()