Biến đổi số
Cho mảng $a$ gồm $n$ số, số thứ $i$ là $a_i$. Bạn có một phép biến đổi như sau: Chọn hai số $a_i$ và $a_j \ (i \neq j)$, nếu $a_i \ge a_j$ thì xóa $a_j$ ra khỏi mảng và $a_i=a_i+1$.
Hãy biến đổi để số lượng số lớn hơn hoặc bằng một giá trị $k$ cho trước là nhiều nhất có thể.
Dữ liệu
- Dòng đầu tiên là hai số nguyên $n$ và $q \ (1\le n,q\le 10^5)$ - số phần tử của mảng và số truy vấn;
- Dòng thứ hai $N$ số nguyên dương $a_i \ (1\le a_i\le 10^9)$ là các phần tử của mảng $a$;
- Dòng thứ $i$ trong $q$ dòng tiếp theo là các giá trị $k_i \ (1\le k_i\le 10^9)$.
Kết quả
- In ra $q$ dòng, dòng thứ $i$ là số phần tử lớn hơn hoặc bằng giá trị $k_i$ nhiều nhất có thể thu được sau khi biến đổi.
Ví dụ
Ví dụ 1
input
5 2
21 9 5 8 10
10
15
output
3
1
Ví dụ 2
input
5 1
1 2 3 4 5
100
output
0
Giải thích
- Test thứ nhất: - Truy vấn 1: Chọn phần tử thứ 2 (giá trị là 9) và thứ 4 (giá trị là 8), sau khi biến đổi ta thu được dãy $(21,10,5,10)$, đây là cách tối ưu.
Truy vấn 2: Dù làm cách nào thì cũng chỉ có một phần tử lớn hơn hoặc bằng 15.
Test thứ hai: - Truy vấn 1: Dù làm cách nào thì không thể tạo ra phần tử lớn hơn hoặc bằng 100.
Comments