Search Insert Position

Binary Search
Array

Given a sorted array of distinct integers nums and a value target, return the index where target is found. If target is not present, return the index where it would be inserted to keep the array sorted. Must run in O(log n).

Examples

Example 1

Input

nums

1

3

5

6

target5

Output

2

Example 2

Input

nums

1

3

5

6

target2

Output

1

Example 3

Input

nums

1

3

5

6

target7

Output

4

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums holds distinct values sorted in ascending order.

Stuck? Hint 1

Standard binary search, but on a miss, return lo — that is the insertion point.

Input

1

3

5

6

target5

Expected Output

Ctrl / ⌘ + Enter

Search Insert Position

Binary Search
Array

Given a sorted array of distinct integers nums and a value target, return the index where target is found. If target is not present, return the index where it would be inserted to keep the array sorted. Must run in O(log n).

Examples

Example 1

Input

nums

1

3

5

6

target5

Output

2

Example 2

Input

nums

1

3

5

6

target2

Output

1

Example 3

Input

nums

1

3

5

6

target7

Output

4

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums holds distinct values sorted in ascending order.

Stuck? Hint 1

Standard binary search, but on a miss, return lo — that is the insertion point.

Input

1

3

5

6

target5

Expected Output

Ctrl / ⌘ + Enter