Tìm vị trí chèn phải

Time limit: 1.0s , Memory limit: 256M , Points: 1 (partial)

Cho một dãy số gồm $n$ ~n~ phần tử $A = \{a_1, a_2, \ldots, a_n\}$ ~A = \{a_1, a_2, \ldots, a_n\}~ được sắp thứ tự tăng dần.

Hãy lập trình tìm vị trí thích hợp (tính từ phải sang) để chèn phần tử $x$ ~x~ vào dãy mà vẫn đảm bảo tính tăng dần.

Dòng đầu tiên chứa hai số nguyên dương $n, x$ ~n, x~ thỏa $1 \le n \le 10^5; 1 \le x \le 10^9$ ~1 \le n \le 10^5; 1 \le x \le 10^9~ .

Dòng tiếp theo chứa các số nguyên $a_i$ ~a_i~ thỏa $1 \le a_i \le 10^9$ ~1 \le a_i \le 10^9~.

In ra vị trí cần tìm. Dãy đánh số thứ tự từ $1$ ~1~

10 4
1 1 2 2 3 3 3 5 6 9

10 9
2 3 4 5 6 9 9 12 19 21

Comments