Vị trí đầu và cuối của phần tử (Find First and Last Position)

Nguồn: LeetCode

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $n$ số nguyên $a_0,a_1,\ldots,a_{n-1}$ đã sắp xếp không giảm và số nguyên target. Hãy tìm chỉ số xuất hiện đầu tiên và cuối cùng của target. Nếu không xuất hiện, in -1 -1. Dãy đánh chỉ số từ $0$. Yêu cầu $O(\log n)$.

Input

Dòng đầu gồm $n$ và target. Dòng hai gồm $n$ số nguyên không giảm; nếu $n=0$ dòng này có thể rỗng.

Output

In first last, hoặc -1 -1 nếu target không xuất hiện.

Subtask

• Subtask 1 — 20%: $0\le n\le100$.
• Subtask 2 — 30%: $0\le n\le10^4$.
• Subtask 3 — 50%: $0\le n\le10^5$, $-10^9\le a_i,\text{target}\le10^9$.

Ví dụ

Input

6 8
5 7 7 8 8 10

Output

3 4

Giải thích

8 xuất hiện từ chỉ số $3$ đến chỉ số $4$, nên kết quả là 3 4.