Binary Search

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return -1. Binary search works by repeatedly dividing the search interval in half. Example: nums=[−1,0,3,5,9,12], target=9 → index 4

Input

Line 1: n (array size). Line 2: n space-separated sorted integers. Line 3: target.

Output

The index of target (0-based), or -1 if not found.

Sample

6
-1 0 3 5 9 12
9

Expected

4