Consider an array A of n distinct integers (that is, all elements are different). It is known that A was originally sorted in ascending order, but A was then right-rotated r places, where 0 < r < n. In other words, the last r elements were moved from the end of the array to the beginning, with all other elements being pushed r positions to the right. For example, for n = 7 and r = 3, the result may look like this:

[43, 46, 58, 12, 20, 29, 34]

For r = 5, the result, based on the same original array, would be

[29, 34, 43, 46, 58, 12, 20]

You know that the given A[0..n1] has this particular form, that is, for some r, the sequence A[r], . . . , A[n 1], A[0], . . . A[r 1] is in ascending order, but you do not know what r is. Design an algorithm to find the largest integer in A. Write an algorithm that works in time O(log n)