768. First and Last
0
Easy
Given a non-decreasing array 'arr' in 0-index based order, find the starting and ending positions of the value 'target' inside the array. Two people, Alex and Nova, want to stand at these positions. If there is no such position, return -1 for both Alex's and Nova's positions. Solve the problem with a time complexity of O(logN).
Input Format
The first line contains an integer N, representing the size of the array.
The second line contains N space-separated integers, representing the elements of the array.
The third line contains the target value as input.
Output Format
Print the required indices where Alex and Nova stand. If there is no such index, print -1 -1.
Example
Input
10
-2 -1 -1 0 3 3 3 3 7 22
3
Output
4 7
Constraints
0 <= N <= 10^9
-10^9 <= target, arr[i] <= 10^9
Loading...
View Submissions
Console