Suppose that you are interested in collecting rainwater to augment a town’s water supply. You know that the water accumulates in valleys (a low altitude point between two higher altitude points), since rain rolls downhill after falling on high points. You want to find the location of one of these valleys, in order to set up a collection point. Assume that the altitude (elevation) is given as a 1D array of numbers at each location (index). For example, here is a possible terrain A=[2, 4, 5, 6, 3, 11, 12, 13, 1, 0, 7], The valleys are A[0], A[4], and A[9]

You are given an array of n elements representing the altitudes of points along the terrain, all of which are distinct. Design an O(log n)-time algorithm that finds the location of a valley. Then