Upper bound (上限)
ソート済みの n 個の整数からなる配列が与えられたとき、q 件のクエリに答えることが求められます。各クエリの内容は「与えられたリストで、x よりも大きい最初の要素は何か？」というものです。
入力
最初の行には、n (2 ≤ n ≤ ) と q (1 ≤ q ≤ ) の 2 つの整数が与えられます。
次の行には、昇順に並んだ n 個の整数 ( ≤ ≤ ) が空白区切りで与えられます。
最後の行には、q 個のクエリ ( ≤ < ) が空白区切りで与えられます。
出力
プログラムは q 行を出力します。各行には、対応するクエリに対する答えを出力してください。
例
入力 | 出力 |
|---|---|
6 3 2 7 9 10 20 30 8 20 1 | 9 30 2 |
Hint
古典的な二分探索の実装では、[l; r) という範囲を用い、l は含み、r は含みません。しかし、場合によっては (l; r] のように l を除外し、r を含む形で実装したいこともあります。その場合、l、r、mid の計算方法を少し変更する必要があります。
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB