Vị trí chèn (Search Insert Position)

Nguồn: LeetCode

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

Đề bài

Cho dãy $n$ số nguyên phân biệt đã sắp xếp tăng dần và target. Nếu target đã có, in chỉ số của nó. Nếu chưa có, in chỉ số mà target phải được chèn vào để dãy vẫn tăng dần. Tương đương, tìm vị trí đầu tiên $i$ sao cho $a_i\ge\text{target}$; nếu không có thì đáp án là $n$. 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 phân biệt tăng dần.

Output

In vị trí của target hoặc vị trí chèn thích hợp.

Subtask

• Subtask 1 — 20%: target nằm ngoài đoạn $[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$.

Ví dụ

Input

4 2
1 3 5 6

Output

1

Giải thích

Chèn 2 vào vị trí $1$ thu được $[1,2,3,5,6]$.