---
tags: 問題
---

# C - Binary Search

実行時間制限 : 2sec / メモリ制限 : 1024MB

配点 : $300$点

## 問題文

長さ$N$の整数列$A = ( A_1,A_2,...,A_N )$と長さ$Q$の整数列$X=(X_1,X_2,...,X_Q)$が与えられます。

各$i$ $(1 \leq i \leq Q)$について、$X_i\leq A_j$を満たす最小の$A_j$ $(1 \leq j \leq N)$を出力しなさい。

ただし、そのような要素が存在しない場合、$-1$を出力しなさい。

## 制約

* $1\leq N,Q \leq 2×10^5$
* $1 \leq A_i \leq 10^9$
* $1 \leq X_i \leq 10^9$

入力はすべて正の整数

## 入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 ... A_N
Q
X_1
X_2
...
X_Q

## 出力

問題文中の指示に従って、$Q$行出力せよ。

## 入力例1

5
1 3 5 7 9
3
3
6
10

## 出力例1

3
7
-1

## 入力例2

7
9 3 4 1 7 8 10
5
1
2
3
4
5

## 出力例2

1
3
3
4
7