Bài 15.2. Chèn Dữ Liệu Sensor - [Độ khó: Dễ]

Bạn là kỹ sư phụ trách hệ thống thu thập dữ liệu từ các cảm biến môi trường. Dữ liệu được lưu trữ trong một mảng đã được sắp xếp tăng dần để dễ dàng truy xuất. Khi một cảm biến mới gửi dữ liệu, bạn cần tìm vị trí chính xác để chèn giá trị mới này vào mảng, sao cho mảng vẫn duy trì tính chất sắp xếp tăng dần. Bạn không cần thực sự chèn nó vào, chỉ cần xác định chỉ số mà nó sẽ được chèn vào. Vị trí chèn được định nghĩa là chỉ số đầu tiên mà tại đó, giá trị trong mảng lớn hơn hoặc bằng giá trị cần chèn.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên N (0 <= N <= 10^5) – số lượng phần tử hiện có trong mảng. Dòng thứ hai chứa N số nguyên A_0, A_1, ..., A_{N-1} (-10^9 <= A_i <= 10^9) – các phần tử của mảng, đảm bảo đã được sắp xếp tăng dần. Dòng thứ ba chứa số nguyên X (-10^9 <= X <= 10^9) – giá trị cần chèn.

OUTPUT FORMAT

In ra chỉ số (0-indexed) mà giá trị X nên được chèn vào.

Ví dụ 1:

Input:

4
10 20 30 40
25

Output:

2

Giải thích:

• Mảng [10, 20, 30, 40]. Giá trị cần chèn X = 25.
• 25 lớn hơn 10 và 20, nhưng nhỏ hơn 30.
• Vị trí chèn thích hợp nhất là trước 30, tức là ở chỉ số 2. Khi chèn, mảng sẽ trở thành [10, 20, 25, 30, 40].

Ví dụ 2:

Input:

5
5 10 15 20 25
30

Output:

5

Giải thích:

• Mảng [5, 10, 15, 20, 25]. Giá trị cần chèn X = 30.
• 30 lớn hơn tất cả các phần tử hiện có.
• Vị trí chèn là cuối mảng, tức là ở chỉ số 5. Khi chèn, mảng sẽ trở thành [5, 10, 15, 20, 25, 30].

Ví dụ 3:

Input:

0

-5

Output:

0

Giải thích:

• Mảng rỗng. Giá trị cần chèn X = -5.
• Vị trí chèn là đầu tiên, tức là ở chỉ số 0.