Find in Mountain Array

Hard

(This problem is an interactive problem.)

An array arr is called a mountain array if and only if:

  • arr.length >= 3
  • There exists some index i with 0 < i < arr.length - 1 such that:
    • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

You are given a mountain array mountainArr and an integer target, return the minimum index such that mountainArr.get(index) == target. If such an index does not exist, return -1.

You cannot access the mountain array directly. You may only access the array using a MountainArray interface:

  • MountainArray.get(k) returns the element of the array at index k (0-indexed).
  • MountainArray.length() returns the length of the array.

You can only make at most 100 calls to the function get(). Submissions making more than 100 calls will be judged as Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example 1:

Input: mountainArr = [2,4,5,2,1], target = 2

Output: 0

Example 2:

Input: mountainArr = [1,2,3,4,2,1], target = 6

Output: -1

Constraints:

  • 3 <= mountainArr.length() <= 10,000
  • 0 <= target, mountainArr.get(index) <= 1,000,000,000

mountainArr =

target =