Find Position in Sorted Array

You are given a sorted array of distinct integers and a target integer. Your task is to find the index of the target in the array. If the target is not present in the array, you should return the index where it can be inserted to maintain the sorted order. Indices are zero-based.

Note: Your solution should use an efficient algorithm (preferably binary search) to achieve optimal performance.

Input Format: The input consists of three lines. The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers denoting the sorted array. The third line contains a single integer representing the target value.

Output Format: Output a single integer indicating the index of the target if it exists, or the index where it should be inserted to keep the array sorted.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

1. The first line contains an integer n — the number of elements in the array.
2. The second line contains n space-separated integers which are sorted in increasing order.
3. The third line contains an integer target — the value to search for in the array.

outputFormat

Print a single integer to standard output (stdout): the index of the target if it exists in the array, or the index where the target can be inserted while maintaining sorted order.

5
1 3 5 6 9
5

2