Help needed in Mo's Algorithm

help
1

Recently I learned Mo’s Algorithm and now I’m trying to solve these two questions from atcoder and spoj but my code gives TLE, can anyone help me in the optimisation of the code.

from sys  import stdin,stdout
from collections  import *
from math import *
st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:map(int,stdin.readline().split())
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

mod=1000000007
INF=float('inf')
d={}

length=0

def ADD(x):
   global length
   if x not in d:
       length+=1
       d[x]=1
   else:
       d[x]+=1
       
def REMOVE(x):
   global length
   if d[x]==1:
       length-=1
       d.pop(x)
   else:
       d[x]-=1
   
   

def solve():
   n,q=mp()
   l=li()
   query=[li()+[i] for i in range(q)]
   P=int(n**0.5)
   query.sort(key=lambda x:(x[0]//P,x[1]))
   curL,curR=0,-1
   ans=[0 for i in range(q)]
   for Q in query:
       left,right,ind=Q
       left-=1
       right-=1
       
       while curL>left:
           curL-=1
           ADD(l[curL])
       
       while curR<right:
           curR+=1
           ADD(l[curR])
   
       while curL<left:
           REMOVE(l[curL])
           curL+=1
           
       while curR>right:
           REMOVE(l[curR])
           curR-=1
       
       ans[ind]=length
       
   print('\n'.join(map(str,ans)))
       
           
   
for _ in range(1):
   solve()

Thanks in advance @ssrivastava990 , @aneee004 , @galencolin , @first_semester , @spaanse