Tìm kiếm nhị phân 4
Cho dãy số nguyên có N phần tử $a_1,a_2,...,a_N$. Biết rằng $a[i]=i^2+1$.
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à $T$ $(1\le N,T \le 10^5)$;
- $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
3 4
1
6
7
11
output
2
10
10
-1
Giải thích
Giải tích:
Dãy a={2,5,10};
Với k=1, có a[1]=2 > 1.
Với k=6, k=7, có a[3]=10 > 6 và a[3]>7.
Với k=11, không tồn tại phần tử thuộc mảng lớn hơn 11.
Comments