First position of a value in a sorted array — interview question

A sorted (non-decreasing) array may contain repeated values. Print the index of the first occurrence of the target, or -1 if it is not present.

Constraints

1 ≤ n ≤ 200000
−10^9 ≤ values ≤ 10^9

Input and output

Input: Line 1: n Line 2: n sorted integers Line 3: target
Output: One integer: the index, or -1.

Examples

Input 1

7
1 2 2 2 5 7 9
2

Output

First 2 at index 1.

Input 2

5
1 3 5 7 9
4

Output

-1

Absent.

Show hints

When you find the target, keep searching to the left.

Show the explanation

Binary search for the first index whose value is ≥ target (a lower bound). If that index is inside the array and holds the target, it is the answer; otherwise print -1. Each step halves the range: O(log n) time, O(1) space. Compute the middle as lo + (hi − lo) / 2 to avoid overflow in languages with fixed-width integers.

Original UniCircle question. Last reviewed 21 Oct 2026.