First Occurrence in a Sorted Array

You are given an array of integers sorted in non-decreasing order and a target value. The array may contain duplicates. Return the 0-based index of the first (leftmost) position at which the target appears. If the target does not appear anywhere in the array, return -1.

Input format

Line 1: an integer n, the length of the array. Line 2: n space-separated integers in non-decreasing order (this line is empty when n = 0). Line 3: an integer target.

Output format

A single integer: the index of the first occurrence of target, or -1 if it is not present.

Constraints

• 0 ≤ n ≤ 100000
• -1000000000 ≤ each array value ≤ 1000000000
• -1000000000 ≤ target ≤ 1000000000
• The array is guaranteed to be sorted in non-decreasing order.