```
class Solution {
public:
int searchInsert(int A[], int n, int target) {
if (!n) return -1;
if (target > A[n-1]) return n;
int low = 0, high = n-1;
while (low < high) {
const int mid = low + (high - low) / 2;
if (A[mid] < target)
low = mid + 1;
else
high = mid;
}
return low;
}
};
```