Cho dãy số nguyên ~a~ gồm ~n~ phần tử và ~q~ truy vấn. Với mỗi truy vấn ~x~, hãy in ra phần tử lớn nhất trong dãy nhỏ hơn ~x~. Nếu không tồn tại phần tử như vậy, in ~-1~.

Dữ liệu vào

Dòng đầu chứa ~n~.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~.

Dòng thứ ba chứa ~q~.

~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~x~.

Dữ liệu ra

Gồm ~q~ dòng, mỗi dòng là đáp án của một truy vấn.

Giới hạn

~1 \le n, q \le 100000~, ~1 \le a_i, x \le 10^{9}~.

Ví dụ

Input

5
1 5 8 5 3
3
5
10
1

Output

3
8
-1