ここでは二分探索を使う問題をいくつか掲載しています。

# A-二分探索1

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

配点 : 100点

## 問題

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

各$i$ $(1 \leq i \leq M)$について，$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

## 出力

$i$行目には$X_i$に対する出力をしてください

## 入力例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

# B-二分探索2

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

配点 : 100点

## 問題

左端を0とする、長さ$10^9$の数直線上に$N$種類の色をつけます。はじめは数直線は色$0$で塗られており、そこに$L_i$ ~ $R_i$の