A coastal authority anchors n wave-height buoys in a fixed straight line along a shipping lane, numbered 0 to n-1 from one end to the other. Each buoy continuously reports a single wave-height reading. A buoy at position i is called a crest buoy if its reading is strictly greater than the reading of the buoy immediately to its left and strictly greater than the reading of the buoy immediately to its right. Because the two end buoys each have only one neighbor, neither end buoy can ever be a crest buoy. Find every crest buoy's position, listed in increasing order.
Line 1: a single integer n, the number of buoys. Line 2: n space-separated integers height[0], height[1], ..., height[n-1], the wave-height reading at each buoy.
Print the 0-indexed positions of all crest buoys, space-separated, in increasing order. If there are no crest buoys, print -1.
1 <= n <= 10^5 1 <= height[i] <= 10^9
Example 1
Input
5 2 6 3 9 4
Expected
1 3
Explanation
Interior positions are 1, 2, and 3. Position 1 has neighbors 2 and 3, and 6 is greater than both, so it is a crest. Position 2 has neighbors 6 and 9, and 3 is not greater than either, so it is not a crest. Position 3 has neighbors 3 and 4, and 9 is greater than both, so it is a crest. The crest buoys are at positions 1 and 3.
Example 2
Input
4 5 5 5 5
Expected
-1
Explanation
Every reading is 5, so no interior buoy has a reading strictly greater than both of its neighbors (all comparisons are ties). There are no crest buoys, so the output is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →