Search Insert Position

Given a sorted list of integers, your task is to determine the index at which a given target integer is located. If the target is not in the list, return the index at which it can be inserted while maintaining the sorted order.

This problem should be solved using an algorithm with logarithmic complexity, specifically \(O(\log n)\), by employing a binary search method.

For example, if the array is [1, 3, 5, 6] and the target is 5, the answer is 2.

inputFormat

The input consists of three lines:

1. The first line contains an integer \(n\), the number of elements in the array.
2. The second line contains \(n\) space-separated integers in ascending order.
3. The third line contains the target integer \(target\).

outputFormat

Output a single integer representing the index where the target is found or where it should be inserted.

4
1 3 5 6
5

2