Upper bound
Dado um array de n inteiros ordenados, é necessário responder a q consultas. Cada consulta pergunta: “Qual é o primeiro número que seja maior que x na lista fornecida?”.
Entrada
A primeira linha da entrada contém dois inteiros n (2 ≤ n ≤ ) e q (1 ≤ q ≤ ).
A linha seguinte contém n inteiros separados por espaço, ( ≤ ≤ ), em ordem crescente.
A última linha contém q consultas separadas por espaço, ( ≤ < ).
Saída
O programa deve imprimir q linhas. Cada linha conterá a resposta para a consulta correspondente.
Exemplos
Entrada | Saída |
|---|---|
6 3 2 7 9 10 20 30 8 20 1 | 9 30 2 |
Dica
Na implementação clássica da pesquisa binária, considera-se o intervalo [l; r), onde l é inclusivo e r é exclusivo. Em alguns casos, pode ser mais conveniente trabalhar com (l; r] — ou seja, excluir l e incluir r. Para isso, é preciso ajustar a forma de calcular l, r e mid.
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB