Find a value in a rotated list

Problem

A sorted list of distinct integers was rotated, for example 30 40 50 10 20. Read a target and print its position (counting from 0), or -1 if it is missing. Use O(log n) time.

Input, output and limits

Input: Line 1: n. Line 2: the n rotated values (all different). Line 3: the target.
Output: One integer: the position, or -1.
Constraints: 1 ≤ n ≤ 10^5
Values are distinct, -10^9 ≤ value, target ≤ 10^9

Examples

Example 1

Input

5
30 40 50 10 20
10

Output

Example 2

Input

5
30 40 50 10 20
35

Output

-1

Hints

Try the problem first. Open one hint at a time.

Hint 1

Around the middle, at least one half is sorted. Test a[lo] ≤ a[mid] to see whether the left half is.

Hint 2

If the target lies inside the sorted half, keep that half. Otherwise keep the other one.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Smallest value in a rotated listmedium
Top of a visitor curvemedium
Orders inside a price rangeeasy
Smallest truck for the parcelsmedium
Smallest bundle that is large enougheasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems