Search Insert Position

The array is sorted and has distinct values. Print the index of target if it is present; otherwise print the index where it would be inserted to keep the array sorted.

Input:

• line 1: n
• line 2: n distinct integers in increasing order
• line 3: target

Output: one index (0-based, between 0 and n).

Constraints: 1 ≤ n ≤ 10⁵, −10⁴ ≤ a[i], target ≤ 10⁴. Aim for O(log n).

Think about it: this is "the first index whose value is ≥ target" — the lower bound. Write the loop so it ends with lo == hi at exactly that index.