Search Insert Position

Source: LeetCode

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$ distinct integers sorted increasingly and target, print its index if present. Otherwise print the index where it must be inserted so the array remains sorted. Equivalently, find the first $i$ with $a_i\ge\text{target}$; if none exists, answer $n$. Required time: $O(\log n)$.

Input

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

Output

Print the position of target or its insertion position.

Subtasks

• Subtask 1 — 20%: target lies outside $[a_0,a_{n-1}]$.
• Subtask 2 — 30%: $1\le n\le1000$.
• Subtask 3 — 50%: $1\le n\le10^4$, $-10^4\le a_i,\text{target}\le10^4$.

Examples

Input

4 2
1 3 5 6

Output

1

Explanation

Inserting 2 at index $1$ produces $[1,2,3,5,6]$.