Tìm kiếm nhị phân 4 (mở rộng)


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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 \le 10^9; 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^18)$.

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

There are no comments at the moment.