Xếp hàng
Xem dạng PDF
Gửi bài giải
Điểm:
0,10 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Trong trường học tiểu học đang diễn ra lễ tổng kết, các giáo viên đang sắp xếp các học sinh của mình thành một hàng có chiều cao tăng dần.
Có ~N~ học sinh đang hiện đã được xếp thành một hàng theo thứ tự chiều cao tăng dần. Hiện đang có ~Q~ học sinh đến trễ, nên khi cứ có một học sinh mới tới thì giáo viên phải xếp học sinh đó vào trước các học sinh cao hơn.
Tuy nhiên, vì để phát quà thuận lợi, giáo viên cần biết rõ vị trí của các học sinh trong hàng. Vì vậy, khi có một học sinh mới vào hàng, hãy giúp giáo viên tìm vị trí của học sinh mới vào đó trong hàng nhé.
Input
- Dòng đầu gồm ~2~ số nguyên dương ~N, Q~ ~(1 \le N, Q \le 5 \cdot 10^5)~ - là số học sinh ban đầu và số học sinh được thêm vào sau đó.
- Dòng thứ ~2~ gồm ~N~ số nguyên dương ~H_1, H_2, \dots H_N~ ~(1 \le H_i \le 10^9)~ - chiều cao của ~N~ học sinh được xếp ban đầu.
- ~Q~ dòng tiếp theo, mỗi dòng gồm một số nguyên dương ~X~ ~(1 \le X \le 10^9)~ - là chiều cao của học sinh đến sau.
Output
- Gồm ~Q~ dòng, dòng thứ ~i~ gồm một số nguyên dương là vị trí của học sinh thứ ~i~ được thêm vào hàng.
Constraints
- Subtask 1 (gồm ~50\%~ số điểm): ~N, Q \le 1000~.
- Subtask 2 (gồm ~50\%~ số điểm): ~N, Q \le 5 \cdot 10^5~.
Sample Input
8 5
2 3 3 5 5 7 7 9
9
5
2
5
3
Sample Output
9
6
2
8
5
Notes
Với trường hợp ví dụ:
- Hàng được xếp ban đầu như sau: 2 3 3 5 5 7 7 9
- Lần lượt các học sinh đến sau là:
- Học sinh thứ nhất: 2 3 3 5 5 7 7 9 9. Vị trí thứ 9.
- Học sinh thứ hai: 2 3 3 5 5 5 7 7 9 9. Vị trí thứ 6.
- Học sinh thứ ba: 2 2 3 3 5 5 5 7 7 9 9. Vị trí thứ 2.
- Học sinh thứ tư: 2 2 3 3 5 5 5 5 7 7 9 9. Vị trí thứ 8.
- Học sinh thứ năm: 2 2 3 3 3 5 5 5 5 7 7 9 9. Vị trí thứ 5.
Bình luận
bài hay
Bài này giải sao mn