Find in Mountain Array

Hard

An array is a mountain array if there is some index peak with 0 < peak < n - 1 such that nums[0] < ... < nums[peak] > ... > nums[n - 1].

Given a mountain array nums and a target, return the smallest index whose value equals the target, or -1 if the target is not present.

The original problem hides the array behind a MountainArray interface with a call budget. Here the array is passed directly, but the intended solution is the same three binary searches — do not scan linearly.

Example 1

Input:  nums = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: The value 3 appears at indices 2 and 5; the smaller index is 2.

Example 2

Input:  nums = [0,1,2,4,2,1], target = 3
Output: -1

Constraints

• 3 <= nums.length <= 10^4
• 0 <= target <= 10^9
• 0 <= nums[i] <= 10^9
• nums is a valid mountain array