Binary Search

Source: LeetCode

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$ distinct integers $a_0,a_1,\ldots,a_{n-1}$ sorted increasingly and an integer target, find its index. Print -1 if it is absent. Indices start at $0$. The required time complexity is $O(\log n)$.

Input

The first line contains $n$ and target. The second line contains $n$ strictly increasing integers.

Output

Print the index of target, or -1 if it is absent.

Subtasks

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

Examples

Input

6 9
-1 0 3 5 9 12

Output

4

Explanation

9 is stored at $a_4$, so the answer is $4$.