Find the Peak

A cycling app records the height of a mountain road at evenly spaced points, from the start to the finish. The road climbs all the way to a single peak and then descends all the way to the end: before the peak every point is lower than the point after it, and after the peak every point is lower than the point before it. The climb or the descent may be missing, so the peak can be the first or the last point.

Write find_peak(heights) that returns the index of the peak (the highest point).

Examples

find_peak([120, 180, 260, 240, 90])  # returns 2
find_peak([500, 410, 300])           # returns 0
find_peak([3, 8, 15, 16])            # returns 3

Constraints

• 1 <= len(heights) <= 10^9
• Neighbouring heights are never equal
• heights is not always a list. You may only use len(heights) and heights[i] for 0 <= i < len(heights). In one test it is a road of a billion points, each worked out only when you ask for it.

Note

Looking at every point of a billion-point road takes far too long. Comparing a point with the next one tells you whether you are on the way up or on the way down, and that is enough to rule out half of the road.