len[1][L_] := -Tr[Unitize[# - L[[ ;; Length[#]]]] - 1] &[
  DeleteDuplicates[L]]
len[2][L_] :=
 Length[#] - Tr[Unitize[L[[;; Length[#]]] - #]] &[DeleteDuplicates[L]]
len[3][L_] :=
 Length[#] - Tr@Unitize@Subtract[L~Take~Length[#], #] &@
  DeleteDuplicates@L
l = {{{}, {}}, {{}, {}}, {{}, {}}};
SeedRandom[42];
Q = RandomInteger[10^6, 10^6];
Do[
  Do[
   (If[i == 2, Q = RandomInteger[10^6, 10^6]];
    Do[
     AppendTo[l[[j, i]], First@AbsoluteTiming[len[j][Q]]],
     {j, 3}
     ]
    ), {50}],
  {i, 2}];
Grid[Transpose@
  Join[{{"", "Not Randomized", "Randomized"}},
   Transpose@
    Join[{{len1, len2, len3}},
     Flatten[{#/#[[1]]} & /@ Transpose[Mean /@ l[[#]] & /@ Range@3],
      1]]]]