Search Insert Position

You are given a sorted array of n integers and a target value. Your task is to find the index of the target if it exists in the array. Otherwise, return the index where the target should be inserted in order to keep the array sorted.

This problem is best solved using a binary search algorithm with a time complexity of \(O(\log n)\). The indices are 0-based. Make sure that your solution works for edge cases, such as an empty array or a target value that is smaller than all elements in the array.

Input and Output via Standard Input/Output (stdin/stdout)

inputFormat

The input consists of three lines:

1. The first line contains an integer n denoting the number of elements in the array.
2. The second line contains n space-separated integers in sorted order. If n is zero, this line may be empty.
3. The third line contains the target integer.

outputFormat

Output a single integer representing the index at which the target is found or should be inserted to maintain sorted order.

4
1 3 5 6
5

2