Find First and Last Position of Element in Sorted Array

Source: LeetCode

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$ integers $a_0,a_1,\ldots,a_{n-1}$ sorted in non-decreasing order and target, find its first and last positions. If absent, print -1 -1. Indices start at $0$. Required time: $O(\log n)$.

Input

The first line contains $n$ and target. The second line contains $n$ non-decreasing integers; it may be empty when $n=0$.

Output

Print first last, or -1 -1 if target is absent.

Subtasks

• 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$.

Examples

Input

6 8
5 7 7 8 8 10

Output

3 4

Explanation

8 occurs from index $3$ through index $4$, so the result is 3 4.