Insert Position in Sorted Array

Given a sorted array of integers and a target value \(V\), your task is to determine the index at which \(V\) is located. If \(V\) does not exist in the array, find the index where it can be inserted while maintaining the array's sorted order.

In other words, if the array is denoted as \(arr\) and is sorted in non-decreasing order, find an index \(i\) such that:

\(\text{for all } j < i, arr[j] < V \quad and \quad (i == n \text{ or } arr[i] \ge V)\)

This problem can be solved efficiently using a binary search algorithm.

inputFormat

The first line contains a single integer \(N\), representing the number of elements in the array.

The second line contains \(N\) space-separated integers denoting the sorted array \(arr\). If \(N = 0\), this line will be empty.

The third line contains a single integer \(V\) which is the target value.

outputFormat

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

## sample

4
1 3 5 6
5

2

</p>