Monte Carlo Algorithm. Will choose correct and clear answer!

Input a sorted array A of length n of arbitrary real numbers. The array might be of two types: 1)All the elements are distinct 2) The array has n copies of one element, the other elements being distinct. Present a Monte carlo algorithm that determines the type of the array in O( n log n) time. Show that the output of your algorithm will be correct with high probability.(You might need: (1 x) 1/x 1/e for any 1 > x > 0.) Prove that your algorithm runs with the desired constraints.