Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



while query:
    lq,rq,j=query.pop()   
    ans[j]=rq-lq+1-(seg.get(lq-1,rq))
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)


Fixed submission:
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i+1:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    # k: index , x: value
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res


C=list(map(int, input().split()))

        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l-1,r-1,i))
query=sorted(query, key=lambda x: -x[1])

A=[0]*(N+1)
def add(a,b):
    return a+b
seg=SegmentTree(A,add,0)
ans=[0]*Q

state=[-1]*N
que=[]
for i in range(N):
    while query and query[-1][1]<i:
        q=query.pop()
        l,r,j=q
        ans[j]=r-l+1-seg.query(l,r+1)
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i
    else:
        A[state[c-1]]+=1
        seg.update(state[c-1], A[state[c-1]])
        state[c-1]=i
        
    while query and query[-1][1]==i:
        q=query.pop()
        lq,rq,j=q
        
        ans[j]=rq-lq+1-seg.query(lq,rq+1)
        #print(lq, rq, seg.query(lq,rq+1))


while query:
    q=query.pop()
    lq,rq,j=q     
    ans[j]=rq-lq+1-seg.query(lq,rq+1)
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)


Fixed submission:
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i+1:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<=x<j
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


C=list(map(int, input().split()))
state=[-1]*N
que=[]
for i in range(N):
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        que.append((state[c-1],i+1))
        state[c-1]=i+1

que=sorted(que, key=lambda x: x[1])
        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

seg=BIT(N+1)
ans=[0]*Q



for i in range(len(que)):
    while query and query[-1][1]<que[i][1]:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    now=que[i]
    l, r=now  # index
    #A[l]+=1
    seg.add(l, 1)

    while query and query[-1][1]==r:
        lq,rq,j=query.pop()
        
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.query(lq,rq+1))
        #print(seg.get(lq,rq+1))

while query:
    lq,rq,j=query.pop()   
    ans[j]=rq-lq+1-(seg.get(lq-1,rq))
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)


Fixed submission:
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i+1:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<=x<j
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


C=list(map(int, input().split()))
state=[-1]*N
que=[]
for i in range(N):
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        que.append((state[c-1],i+1))
        state[c-1]=i+1

que=sorted(que, key=lambda x: x[1])
        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

seg=BIT(N+1)
ans=[0]*Q



for i in range(len(que)):
    while query and query[-1][1]<que[i][1]:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    now=que[i]
    l, r=now  # index
    #A[l]+=1
    seg.add(l, 1)

    while query and query[-1][1]==r:
        lq,rq,j=query.pop()
        
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.query(lq,rq+1))
        #print(seg.get(lq,rq+1))

while query:
    lq,rq,j=query.pop()   
    ans[j]=rq-lq+1-(seg.get(lq-1,rq))
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)


Fixed submission:
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i+1:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<=x<j
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


C=list(map(int, input().split()))
state=[-1]*N
que=[]
for i in range(N):
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        que.append((state[c-1],i+1))
        state[c-1]=i+1

que=sorted(que, key=lambda x: x[1])
        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

seg=BIT(N+1)
ans=[0]*Q



for i in range(len(que)):
    while query and query[-1][1]<que[i][1]:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    now=que[i]
    l, r=now  # index
    #A[l]+=1
    seg.add(l, 1)

    while query and query[-1][1]==r:
        lq,rq,j=query.pop()
        
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.query(lq,rq+1))
        #print(seg.get(lq,rq+1))

while query:
    lq,rq,j=query.pop()   
    ans[j]=rq-lq+1-(seg.get(lq-1,rq))
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)


Fixed submission:
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i+1:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<=x<j
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


C=list(map(int, input().split()))
state=[-1]*N
que=[]
for i in range(N):
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        que.append((state[c-1],i+1))
        state[c-1]=i+1

que=sorted(que, key=lambda x: x[1])
        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

seg=BIT(N+1)
ans=[0]*Q



for i in range(len(que)):
    while query and query[-1][1]<que[i][1]:
        q=query.pop()
        l,r,j=q
        ans[j]=r-l+1-(seg.get(l-1,r))

    now=que[i]
    l, r=now  # index
    #A[l]+=1
    seg.add(l, 1)

    while query and query[-1][1]==r:
        q=query.pop()
        lq,rq,j=q
        
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.query(lq,rq+1))
        #print(seg.get(lq,rq+1))

while query:
    q=query.pop()
    lq,rq,j=q     
    ans[j]=rq-lq+1-(seg.get(lq-1,rq))
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)


Fixed submission:
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i+1:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    # k: index , x: value
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res


C=list(map(int, input().split()))
state=[-1]*N
que=[]
for i in range(N):
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i
    else:
        que.append((state[c-1],i))
        state[c-1]=i

que=sorted(que, key=lambda x: x[1])
        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l-1,r-1,i))
query=sorted(query, key=lambda x: -x[1])

A=[0]*(N+1)
def add(a,b):
    return a+b
seg=SegmentTree(A,add,0)
ans=[0]*Q



for i in range(len(que)):
    while query and query[-1][1]<que[i][1]:
        q=query.pop()
        l,r,j=q
        ans[j]=r-l+1-seg.query(l,r+1)

    now=que[i]
    l, r=now  # index
    A[l]+=1
    seg.update(l, A[l])

    while query and query[-1][1]==r:
        q=query.pop()
        lq,rq,j=q
        
        ans[j]=rq-lq+1-seg.query(lq,rq+1)
        #print(lq, rq, seg.query(lq,rq+1))

while query:
    q=query.pop()
    lq,rq,j=q     
    ans[j]=rq-lq+1-seg.query(lq,rq+1)
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)

Fixed submission:
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i+1:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    # k: index , x: value
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res


C=list(map(int, input().split()))
state=[-1]*N
que=[]
for i in range(N):
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i
    else:
        que.append((state[c-1],i))
        state[c-1]=i

que=sorted(que, key=lambda x: x[1])
        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l-1,r-1,i))
query=deque(sorted(query, key=lambda x: x[1]))

A=[0]*(N+1)
def add(a,b):
    return a+b
seg=SegmentTree(A,add,0)
ans=[0]*Q



for i in range(len(que)):
    while query and query[0][1]<que[i][1]:
        q=query.popleft()
        l,r,j=q
        ans[j]=r-l+1-seg.query(l,r+1)

    now=que[i]
    l, r=now  # index
    A[l]+=1
    seg.update(l, A[l])

    while query and query[0][1]==r:
        q=query.popleft()
        lq,rq,j=q
        
        ans[j]=rq-lq+1-seg.query(lq,rq+1)
        #print(lq, rq, seg.query(lq,rq+1))

while query:
    q=query.popleft()
    lq,rq,j=q     
    ans[j]=rq-lq+1-seg.query(lq,rq+1)
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)


Fixed submission:
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i+1:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



for a in ans:
    print(a)