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

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_all=[[] for _ in range(n+1)]
for i in range(n):
  val=arr[i]
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=0
  pos_all[val].append(i+1)
for i in range(n+1):
  pos_all[i].append(-1)
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if pos_all[val][pos_now[val]+1]!=-1:
      pos_now[val]+=1
      bit.add(pos_all[val][pos_now[val]],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Fixed submission:
import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_prev=[-1]*(n+1)
dic={}
for i in range(n):
  val=arr[i]
  dic[i+1]=-1
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=i+1
  if pos_prev[val]!=-1:
    dic[pos_prev[val]]=i+1
  pos_prev[val]=i+1
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if dic[pos_now[val]]!=-1:
      pos_now[val]=dic[pos_now[val]]
      bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

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

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_all=[[] for _ in range(n+1)]
for i in range(n):
  val=arr[i]
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=0
  pos_all[val].append(i+1)
for i in range(n+1):
  pos_all[i].append(-1)
cnt=collections.Counter(arr)
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if pos_all[val][pos_now[val]+1]!=-1:
      pos_now[val]+=1
      bit.add(pos_all[val][pos_now[val]],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Fixed submission:
import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_prev=[-1]*(n+1)
dic={}
for i in range(n):
  val=arr[i]
  dic[i+1]=-1
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=i+1
  if pos_prev[val]!=-1:
    dic[pos_prev[val]]=i+1
  pos_prev[val]=i+1
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if dic[pos_now[val]]!=-1:
      pos_now[val]=dic[pos_now[val]]
      bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

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

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_all=[[] for _ in range(n+1)]
for i in range(n):
  val=arr[i]
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=0
  pos_all[val].append(i+1)
for i in range(n+1):
  pos_all[i].append(-1)
cnt=collections.Counter(arr)
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if cnt[val]!=1:
      bit.add(pos_all[val][pos_now[val]],-1)
      if pos_all[val][pos_now[val]+1]!=-1:
        pos_now[val]+=1
        bit.add(pos_all[val][pos_now[val]],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Fixed submission:
import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_prev=[-1]*(n+1)
dic={}
for i in range(n):
  val=arr[i]
  dic[i+1]=-1
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=i+1
  if pos_prev[val]!=-1:
    dic[pos_prev[val]]=i+1
  pos_prev[val]=i+1
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if dic[pos_now[val]]!=-1:
      pos_now[val]=dic[pos_now[val]]
      bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

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

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_all=[[] for _ in range(n+1)]
for i in range(n):
  val=arr[i]
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=0
  pos_all[val].append(i+1)
for i in range(n+1):
  pos_all[i].append(-1)
cnt=collections.Counter(arr)
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if cnt[val]!=1:
      bit.add(pos_all[val][pos_now[val]],-1)
      if pos_all[val][pos_now[val]+1]!=-1:
        pos_now[val]+=1
        bit.add(pos_all[val][pos_now[val]],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Fixed submission:
import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_prev=[-1]*(n+1)
dic={}
for i in range(n):
  val=arr[i]
  dic[i+1]=-1
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=i+1
  if pos_prev[val]!=-1:
    dic[pos_prev[val]]=i+1
  pos_prev[val]=i+1
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if dic[pos_now[val]]!=-1:
      pos_now[val]=dic[pos_now[val]]
      bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

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

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[list(map(int,input().split()))+[i] for i in range(q)]
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_next=[[] for _ in range(n+1)]
for i in range(n):
  val=arr[i]
  if pos_now[val]==-1:
    pos_now[val]=i+1
    bit.add(i+1,1)
  else:
    pos_next[val].append(i+1)
cnt=collections.Counter(arr)
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if cnt[val]!=1:
      bit.add(pos_now[val],-1)
      if len(pos_next[val])!=0:
        pos_now[val]=pos_next[val][0]
        pos_next[val]=pos_next[val][1:]
        bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Fixed submission:
import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_prev=[-1]*(n+1)
dic={}
for i in range(n):
  val=arr[i]
  dic[i+1]=-1
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=i+1
  if pos_prev[val]!=-1:
    dic[pos_prev[val]]=i+1
  pos_prev[val]=i+1
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if dic[pos_now[val]]!=-1:
      pos_now[val]=dic[pos_now[val]]
      bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import sys
input=sys.stdin.readline

class SegmentTreeSet():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=self.tree[pos]|val
    while pos>1:
      pos=pos//2
      self.tree[pos]=self.tree[2*pos]|self.tree[2*pos+1]
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=ret|self.tree[r]
      r=(r-1)//2
      ret=ret|self.tree[l]
      l=(l+1)//2
    return ret

n,q=map(int,input().split())
arr=list(map(int,input().split()))
st=SegmentTreeSet(n,set())
for i in range(n):
    tmp=set()
    tmp.add(arr[i])
    st.update(i,tmp)
for _ in range(q):
    l,r=map(int,input().split())
    l-=1
    r-=1
    print(len(st.query(l,r)))


Fixed submission:
import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_prev=[-1]*(n+1)
dic={}
for i in range(n):
  val=arr[i]
  dic[i+1]=-1
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=i+1
  if pos_prev[val]!=-1:
    dic[pos_prev[val]]=i+1
  pos_prev[val]=i+1
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if dic[pos_now[val]]!=-1:
      pos_now[val]=dic[pos_now[val]]
      bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)