Array.prototype.swap=function(B,A){var C=this[B];
this[B]=this[A];
this[A]=C
};
Number.prototype.compareTo=function(A){return this-A
};
var SortUtils={};
SortUtils.binarySearchNextIndex=function(D,C,A){function B(E,J,G,M,I){var H=I-M;
if(H==0){return M
}if(H==1){return(G(E[M],J)<0)?M+1:M
}var L=(H-H%2)/2;
var F=H%2==0;
var K=M+L-((F)?1:0);
if(G(E[K],J)<0){return B(E,J,G,K+1,I)
}else{return B(E,J,G,M,K)
}}if(D.length==0){return 0
}return B(D,C,A,0,D.length)
};
SortUtils.partition=function(G,E,C,B){var F=G[B];
G.swap(B,C-1);
var D=E;
var A;
for(A=E;
A<C-1;
++A){if(G[A].compareTo(F)<=0){G.swap(D,A);
++D
}}G.swap(C-1,D);
return D
};
SortUtils.qsort=function(D,C,B){if(B-1>C){var A=C+Math.floor(Math.random()*(B-C));
A=SortUtils.partition(D,C,B,A);
SortUtils.qsort(D,C,A);
SortUtils.qsort(D,A+1,B)
}};
SortUtils.sort=function(A){SortUtils.qsort(A,0,A.length)
};