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.)