First and Last Position in Sorted Array

Problem statement

A sorted event log can contain repeated identifiers. For a requested identifier, find the first and last occupied positions in the log. If the identifier does not occur, return -1 for both positions. Use logarithmic search rather than scanning all matches.

Input format

First line: n target. Second line: n sorted integers.

Output format

Print first_index last_index using zero-based indices, or -1 -1.

Constraints

1 <= n <= 100000; values and target are between -1000000000 and 1000000000.

Sample input

6 4
1 2 4 4 4 9

Sample output

2 4