Tìm kiếm nhị phân 3
Cho dãy số nguyên có N phần tử $a_1,a_2,...,a_N$. Cho $T$ truy vấn, mỗi truy vấn là một số nguyên $k$. Hãy tìm trong dãy $a$ phần tử nhỏ nhất có giá trị lớn hơn $k$.
Dữ liệu
- Dòng duy nhất chứa hai số nguyên dương $N$ và $Q$ $(1\le N,T \le 10^5)$;
- Dòng tiếp theo chứa $N$ số nguyên $a_i$ $(1\le a_i \le 10^9)$;
- $T$ dòng tiếp theo, mỗi dòng chứa một số nguyên $k$ $(1 \le k \le 10^9)$.
Kết quả
- In kết quả của $T$ truy vấn trên $T$ dòng, nếu tồn tại kết quả, in ra giá trị đó, ngược lại in \t{-1}.
Ví dụ
Ví dụ 1
input
5 3
1 6 4 3 2
5
7
3
output
6
-1
4
Giải thích
Với truy vấn đầu tiên: $k=5$, phần tử thứ 2 của mảng có giá trị là 6 - là phần tử nhỏ nhất và lớn hơn 5.
Với truy vấn thứ hai: $k=7$, trong mảng không có giá trị nào lớn hơn 7.
Với truy vấn thứ ba: $k=3$, có $a[3]=4 > 3$.
Comments