Find First and Last Position in Sorted Array

Given a sorted array of integers and a target value, your task is to determine the first and last positions (0-indexed) at which the target value appears in the array. If the target value is not found, you should output -1 -1.

This problem is often solved using binary search. Suppose the sorted array is \(A\) and the target value is \(T\). You need to find indices \(i\) and \(j\) such that \(A[i] = T\) and \(A[j] = T\) with \(i\) as the smallest index and \(j\) as the largest index. If no such indices exist, output \(-1 -1\).

inputFormat

The first line contains two integers, \(n\) and \(target\), where \(n\) is the number of elements in the array.

The second line contains \(n\) space-separated integers, sorted in non-decreasing order. If \(n = 0\), the second line will be empty.

outputFormat

Output two space-separated integers representing the first and last positions (0-indexed) of the target value. If the target is not found, output -1 -1.

6 8
5 7 7 8 8 10

3 4