Buggy python submission (verdict: Runtime Error):
from operator import itemgetter
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
a=position_zip(a,0)
k=max(a)+1
ans=[0]*q
queries=[list(map(lambda x:int(x)-1,input().split()))+[i]for i in range(q)]
queries.sort(key=itemgetter(1))
queries.append([0,0,0])
lastAppeared=[-1]*k
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]]!=-1:
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  while queries[j][1]==i:
    l,r,ind=queries[j]
    j+=1
    ans[ind]=bitt.sum(l,r-1)
print(*ans)


Fixed submission:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Runtime Error):
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(n):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Fixed submission:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    queries.append([r-1,l-1,i])
  ans=[0]*q
  queries.sort()
  queries.append([10*20,0,0])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Fixed submission:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
n,q,*x=map(int,open(0).read().split())
a=x[:n]
queries=[]
for i in range(q):
  l,r=x[n+i*2:n+(i+1)*2]
  queries.append([r-1,l-1,i])
ans=[0]*q
queries.sort()
queries.append([10*20,0,0])
lastAppeared=[-1]*n
bit=[0]*n
def add(i,x):
  i+=1
  while i<=n:
    bit[i-1]+=x
    i+=i&-i
def sum_sub(i):
  a=0
  i+=1
  while i:
    a+=bit[i-1]
    i-=i&-i
  return a
def sum(i,j):
  a=sum_sub(j+1)
  if i!=0:a-=sum_sub(i-1)
  return a
j=0
for i in range(n):
  if lastAppeared[a[i]-1]!=-1:
    add(lastAppeared[a[i]-1],-1)
    add(i,1)
    lastAppeared[a[i]-1]=i
  else:
    add(i,1)
    lastAppeared[a[i]-1]=i
  while queries[j][0]==i:
    r,l,ind=queries[j]
    j+=1
    ans[ind]=sum(l,r-1)
print(*ans)


Fixed submission:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q,*x=map(int,open(0).read().split())
a=x[:n]
queries=[]
for i in range(q):
  l,r=x[n+i*2:n+(i+1)*2]
  queries.append([r-1,l-1,i])
ans=[0]*q
queries.sort()
queries.append([10*20,0,0])
lastAppeared=[-1]*n
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]-1]!=-1:
    bitt.add(lastAppeared[a[i]-1],-1)
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  while queries[j][0]==i:
    r,l,ind=queries[j]
    j+=1
    ans[ind]=bitt.sum(l,r-1)
print(*ans)


Fixed submission:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
def main():
  n,q,*a=map(int,open(0).read().split())
  ans=[0]*q
  queries=[]
  for i in range(q):queries.append((a[n+i*2+1]-1,a[n+i*2]-1,i))
  queries.sort()
  queries.append((10**20,0,0))
  lastAppeared=[n]*n
  bitt=BinaryIndexedTree(n+1)
  j=0
  for i in range(n):
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=bitt.sum(l,r-1)
  print(*ans)

if __name__ == "__main__":
  main()

Fixed submission:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
def main():
  n,q=map(int,input().split())
  a=list(map(lambda x:int(x)-1,input().split()))
  ans=[0]*q
  queries=[]
  for i in range(q):
    l,r=map(int,input().split())
    queries.append((r-1,l-1,i))
  queries.sort()
  queries.append((10**20,0,0))
  lastAppeared=[n]*n
  bitt=BinaryIndexedTree(n+1)
  j=0
  for i in range(n):
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=bitt.sum(l,r-1)
  print(*ans)

if __name__ == "__main__":
  main()

Fixed submission:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
  import sys
  input=sys.stdin.readline
  class BinaryIndexedTree:
    def __init__(self,n):
      self.bit=[0]*n
    def add(self,i,x):
      i+=1
      while i<=len(self.bit):
        self.bit[i-1]+=x
        i+=i&-i
    def sum_sub(self,i):
      a=0
      i+=1
      while i:
        a+=self.bit[i-1]
        i-=i&-i
      return a
    def sum(self,i,j):
      a=self.sum_sub(j+1)
      if i!=0:a-=self.sum_sub(i-1)
      return a
  n,q=map(int,input().split())
  a=list(map(lambda x:int(x)-1,input().split()))
  ans=[0]*q
  queries=[list(map(lambda x:int(x)-1,input().split()))[::-1]+[i]for i in range(q)]
  queries.sort()
  queries.append((10**20,0,0))
  lastAppeared=[-1]*n
  bitt=BinaryIndexedTree(n)
  j=0
  for i in range(n):
    if lastAppeared[a[i]]!=-1:
      bitt.add(lastAppeared[a[i]],-1)
      bitt.add(i,1)
      lastAppeared[a[i]]=i
    else:
      bitt.add(i,1)
      lastAppeared[a[i]]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=bitt.sum(l,r-1)
  print(*ans)

if __name__ == "__main__":
  main()

Fixed submission:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
a=position_zip(a,0)
k=max(a)+1
ans=[0]*q
queries=[list(map(lambda x:int(x)-1,input().split()))[::-1]+[i]for i in range(q)]
queries.sort()
queries.append([10*20,0,0])
lastAppeared=[-1]*k
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]]!=-1:
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  while queries[j][0]==i:
    r,l,ind=queries[j]
    j+=1
    ans[ind]=bitt.sum(l,r-1)
print(*ans)

Fixed submission:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
a=position_zip(a,0)
k=max(a)+1
ans=[0]*q
queries=[list(map(lambda x:int(x)-1,input().split()))[::-1]+[i]for i in range(q)]
queries.sort()
queries.append([10*20,0,0])
lastAppeared=[-1]*k
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]]!=-1:
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  while queries[j][0]==i:
    r,l,ind=queries[j]
    j+=1
    ans[ind]=bitt.sum(l,r-1)
print(*ans)

Fixed submission:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()