{q-,r-,s-,d-,i-}
const maxn=1 shl 20;zero=ord('0');
var t:Text;
   V,A,B:array[0..maxn]of longword;s:string;
   unde,n,la,lb,i,j,pas,lg:longint;last,x:longword;
   ok:boolean;
   return:int64;
   procedure init;
   begin
      assign(T,'secv5.in');reset(T);readln(t,n,la,lb);
      for i:=1 to N do
      begin
         readln(t,S);
         for pas:=1 to length(s) do V[i]:=V[i]*10+ord(S[pas])-zero;
      end;close(t);
   end;
   Procedure Qsort(lo,hi:longint;var a:array of longword);
   var i,j:longint;
   begin
      i:=lo;j:=hi;x:=V[A[(lo+hi)div 2]];
      repeat
         while V[A[i]]<x do inc(i);while x<V[A[j]]do dec(j);
         if i<=j then begin A[0]:=a[i];a[i]:=A[j];a[j]:=A[0];inc(i);dec(j)end;
      until i>j;
      if lo<j then qsort(lo,j,a);if i<hi then qsort(i,hi,a);
   end;
   Procedure mergesort(lo,hi:longint;var a,b:array of longword);
   var juma:longint;
   begin
      if hi-lo<=128 then
      begin
         for i:=lo to hi do A[i]:=i;
         Qsort(lo,hi,a);
      end else
{      if lo=hi then A[lo]:=lo else}
      begin
         juma:=(lo+hi)div 2;mergesort(lo,juma,b,a);mergesort(juma+1,hi,b,a);
         i:=lo;j:=juma+1;
         for lg:=lo to hi do if (j>hi)or(i<=juma)and(V[B[i]]<=V[B[j]]) then
         begin A[lg]:=B[i];inc(i);end else begin A[lg]:=b[j];inc(j);end;
      end;
   end;
   procedure get(limit:longint);
   begin
      i:=1;lg:=0;fillchar(a,sizeof(A),0);
      for pas:=1 to N do
      begin
         while (i<=N)and(lg<=limit)do
         begin if A[B[i]]=0 then inc(lg);inc(A[B[i]]);inc(i);end;
         if lg<=limit then inc(return,i) else inc(return,i-1);
         dec(A[B[pas]]);
         if A[B[pas]]=0 then dec(lg);
      end;
   end;
{var t1:longint;t2:longint absolute $0:$046c;}
begin
{   t1:=t2;}
   init;
{   writeln((t2-t1)/18.2:0:6);
   mergesort(1,N,A,B);
{   for i:=1 to 1000 do write(V[A[i]],' ');writeln;}
   writeln((t2-t1)/18.2:0:6);
   last:=V[A[1]];lg:=1;
   for i:=1 to N do if V[A[i]]=last then B[A[i]]:=lg else
   begin inc(lg);last:=V[A[i]];B[A[i]]:=lg;end;
   writeln((t2-t1)/18.2:0:6);
   get(lb);return:=-return;get(la-1);
   assign(t,'secv5.out');rewrite(T);writeln(T,-return);close(T);
   writeln((t2-t1)/18.2:0:6);}
end.