Tenemos un arreglo de N enteros que ya está ordenado de menor a mayor (o más estrictamente, está ordenado en orden no decreciente).
Dado un entero arbitrario X, queremos responder esta pregunta: ¿Cuál es el índice del primer elemento de izquierda a derecha que es mayor a X?
Escribe un programa que recibe varias "consultas", cada una con un valor diferente de X y para cada consulta imprime dicho índice.
En este problema asumimos que el índice del primer elemento del arreglo es 0 (al igual que en C).
Por ejemplo, supongamos que tenemos el arreglo A = [1, 2, 4, 7, 7, 10] y X = 5. El primer elemento de A mayor a 5 es el primer 7. El índice de este elemento es 3, entonces la salida en este caso debe ser 3.
Si X es suficientemente grande, es posible que no exista ningún elemento mayor a X en el arreglo. En ese caso, tu programa debe imprimir N (el tamaño del arreglo).
La entrada contiene varias líneas:
N, el número de elementos en el arreglo.N enteros Ai para 0 ≤ i < N, los elementos del arreglo. Estos números están separados por espacios. Está garantizado que Ai satisface -109 ≤ Ai ≤ 109. Está garantizado que el arreglo está ordenado en orden no decreciente (es decir, Ai ≤ Ai+1 para todo 0 ≤ i < N-1).C, el número de consultas.C líneas, cada una con un consulta descrita por un entero X. Está garantizado que -109 ≤ X ≤ 109.La salida debe tener exactamente C líneas (una por consulta).
Para cada consulta, escribe el índice del primer elemento del arreglo que es mayor a X. Si no existe ningún elemento mayor a X, escribe N (el tamaño del arreglo).
6
1 2 4 7 7 10
4
5
-1
100
7
3
0
6
5
La entrada nos da un arreglo A = [1, 2, 4, 7, 7, 10] con 6 elementos. Luego nos dan 4 consultas:
X = 5. Este es el caso explicado más arriba. El primer elemento del arreglo mayor a 5 es el primer 7, y su índice es 3, entonces la salida para esta consulta es 3.X = -1. El primer elemento del arreglo mayor a -1 es 1, y su índice es 0.X = 100. No hay ningún elemento en A que sea mayor a 100, entonces la respuesta es N, que en este caso es 6.X = 7. El primer elemento mayor a 7 es 10, y su índice es 5.1 ≤ N ≤ 100,000 y 1 ≤ C ≤ 50,000.