Search Insert Position

Problem statement

A museum keeps unique exhibit numbers in increasing order. A new catalog lookup either locates an existing exhibit or finds the exact position where a missing exhibit should be inserted without disturbing that order. Your task Return the zero-based index of target if present in the strictly increasing array. Otherwise return the index where inserting target would preserve the sorted order. Use O(log n) time. Important details The insertion position may be zero or n. Do not modify the catalog or output the nearest exhibit value. The target is compared numerically, including when values are negative. Worked example For catalog 2, 5, 8, 12 and target 7, the target belongs between 5 and 8. Its insertion index is 2.

Input format

The first line contains n and target. The next line contains n sorted distinct integers.

Output format

Print one zero-based index.

Constraints

1 <= n <= 10000; -10000 <= values, target <= 10000.

Sample input

4 7
2 5 8 12

Sample output

2