375. 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. Alex and Nova want to stand at these positions. If there are no such positions, 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 elements of the array. The third line contains the target value.

Output Format

Print the required indices where Alex and Nova stand. If there are no such indices, 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