class Solution:
  def search(self, arr, key):

    def find_peak_index():
      b, e = 0, len(arr) - 1
      while b <= e:
        m = (b + e) // 2
        if m + 1 < len(arr) and arr[m] < arr[m + 1]:
          b = m + 1
        else:
          e = m - 1 
      return b   

    def seach_item(peak_index, is_left_search):
      if is_left_search:
        b, e = 0, peak_index
      else:
        b, e = peak_index, len(arr) - 1
        
      while b <= e:
        m = (b + e) // 2
        if arr[m] == key:
          return m 
        elif arr[m] < key:
          b = m + 1
        else:
          e = m - 1
      return -1

    peak_index = find_peak_index()
    left_search = seach_item(peak_index, True)
    return left_search if left_search != -1 else seach_item(peak_index, False)