Elearning CodePath – CTP Online Judge

Vị trí chèn đầu tiên

TKM05

## Đề bài

Cho một mảng `A` gồm `n` số nguyên đã được sắp xếp không giảm.

Có `q` câu hỏi. Mỗi câu hỏi cho một số `x`, hãy tìm vị trí đầu tiên `i` sao cho `Ai >= x`.

Nếu không tồn tại vị trí như vậy, in ra `n + 1`.

Nói cách khác, đây là vị trí có thể chèn `x` vào mảng để mảng vẫn không giảm, và phải là vị trí sớm nhất.

## Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên `n` và `q`.

Dòng thứ hai chứa `n` số nguyên `A1, A2, ..., An`, thỏa mãn `A1 <= A2 <= ... <= An`.

`q` dòng tiếp theo, mỗi dòng chứa một số nguyên `x`.

## Dữ liệu ra

Với mỗi câu hỏi, in ra vị trí đầu tiên `i` sao cho `Ai >= x`, hoặc `n + 1` nếu không có.

## Ràng buộc

- `1 <= n <= 200000`
- `1 <= q <= 200000`
- `-10^9 <= Ai, x <= 10^9`
- Mảng đã được sắp xếp không giảm.

## Subtask

- Subtask 1: `n <= 100`, `q <= 100`.
- Subtask 2: `n <= 5000`, `q <= 5000`.
- Subtask 3: `n <= 200000`, `q <= 200000`.

## Ví dụ

### Input
```text
6 5
2 4 4 7 9 12
1
4
5
13
12
```

### Output
```text
1
2
4
7
6
```

## Giải thích ví dụ

Với `x = 4`, vị trí đầu tiên có giá trị `>= 4` là vị trí `2`. Với `x = 13`, không có phần tử nào đủ lớn nên in `7 = n + 1`.

✅ Đã AC: 6 / 18 submissions