Challenge: Search in a Rotated List

Problem statement

Given a sorted list of n integers that has been rotated an unknown number of times, write some code to find an element in the list. You may assume that the list was originally sorted in an ascending order.

Input

A sorted list that has been rotated a number of times

Output

The index of the element

Sample input

lst = [7, 8, 9, 0, 3, 5, 6]
n = size of the list
key = 3 # Element that is being searched for

Sample output

result = 4 # Index of the element that was searched for