Buggy python submission (verdict: Time Limit Exceeded):
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    NUM[c].append(i)
NUMIND=[0]*(N+1)

# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for x in NUM[1:]:
    if x:
        update(x[0],1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")

Fixed submission:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")

Buggy python submission (verdict: Time Limit Exceeded):
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    NUM[c].append(i)
NUMIND=[0]*(N+1)

# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for x in NUM[1:]:
    if x:
        update(x[0],1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

print(*ANS)

Fixed submission:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")

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

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    NUM[c].append(i)
NUMIND=[0]*(N+1)

# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for x in NUM[1:]:
    if x:
        update(x[0],1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

print(*ANS)

Fixed submission:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")

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

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]

from operator import itemgetter
QU.sort(key=itemgetter(0))

from collections import deque

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    NUM[c].append(i)
NUMIND=[0]*(N+1)

# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for x in NUM[1:]:
    if x:
        update(x[0],1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

print(*ANS)
        
    


Fixed submission:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")

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

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]

from operator import itemgetter
QU.sort(key=itemgetter(0))

from collections import deque

NUM=[deque() for i in range(N+1)]
for i,c in enumerate(C):
    NUM[c].append(i+1)

# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for x in NUM:
    if x:
        update(x[0],1)

ANS=[-1]*Q

ia=0
for x,y,ind in QU:

    while ia+1!=x:
        update(C[ia+1],-1)
        NUM[C[ia+1]].popleft()
        if NUM[C[ia+1]]:
            update(NUM[C[ia+1]][0],1)
        ia+=1
    ANS[ind]=getvalue(y+1)-1

print(*ANS)
        
    


Fixed submission:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")

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

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

LEN=N
Sparse_table = [[1<<c for c in C]]

for i in range(LEN.bit_length()-1):
    j = 1<<i
    B = []
    for k in range(len(Sparse_table[-1])-j):
        B.append(Sparse_table[-1][k]|Sparse_table[-1][k+j])
    Sparse_table.append(B)

def query(l,r):
    i=(r-l).bit_length()-1 # 何番目のSparse_tableを見るか. 

    ANS=Sparse_table[i][l]|Sparse_table[i][r-(1<<i)]

    return bin(ANS).count("1")

for qu in range(Q):
    x,y=map(int,input().split())
    print(query(x-1,y))


Fixed submission:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")

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

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

def seg_function(x,y): # Segment treeで扱うfunction
    return x|y

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
SEG=[set()]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

for i in range(N): # Aを対応する箇所へupdate
    SEG[i+seg_el]={C[i]}

for i in range(seg_el-1,0,-1): # 親の部分もupdate
    SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el): # A[n]をxへ更新（反映）
    i=n+seg_el
    SEG[i]=x
    i>>=1 # 子ノードへ
    
    while i!=0:
        SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r): # 区間[l,r)に関するseg_functionを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=set()

    while L<R:
        if L & 1:
            ANS=seg_function(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=seg_function(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

for i in range(Q):
    x,y=map(int,input().split())
    print(len(getvalues(x-1,y)))


Fixed submission:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")