En la avenida principal de Ciudad Codeo hay N
edificios numerados de 0
a N-1.
Los edificios podrían tener diferentes alturas (aunque también es posible que haya edificios con exactamente la misma altura). Aquí hay un ejemplo con N = 8
. Los números en el eje vertical a la izquierda muestran la altura de los edificios, y los números en la escala horizontal abajo muestran la numeración de los edificios:
En Ciudad Codeo están grabando una película y para la última escena quieren poner una cámara en el edificio más alto que puedan encontrar, siempre y cuando el edificio no esté demasiado lejos de la acción. Más específicamente, el director de la película escoge un rango de edificios descrito por dos números L
y R
(que cumplen 0 ≤ L ≤ R < N
) y quiere encontrar el edificio más alto entre todos los edificios en ese rango (es decir, el edificio más alto entre todos los edificios cuyo número es mayor o igual a L
y menor o igual a R
).
Escribe un programa que recibe la altura de todos los edificios y varias consultas (cada una con valores diferentes de L
y R
). Para cada consulta, tu programa debe encontrar el número del edificio más alto en ese rango.
Aquí hay un ejemplo con L = 2
y R = 5
. Los edificios 2
, 3
, 4
y 5
están dentro del rango y se muestran resaltados en la imagen. El edificio más alto entre ellos es el edificio número 3
(que tiene altura 6
y está señalado por una flecha en la imagen):
La entrada contiene varias líneas:
N
, el número de edificios en la avenida (1 ≤ N ≤ 100,000
).N
enteros Ai
para 0 ≤ i < N
, la altura de todos los edificios de izquierda a derecha. Estos números están separados por espacios. Está garantizado que Ai
satisface 1 ≤ Ai ≤ 109
.C
, el número de consultas (1 ≤ C ≤ 1000
).C
líneas, cada una con un consulta descrita por dos enteros L
y R
. Está garantizado que 0 ≤ L ≤ R < N
(es decir, L
y R
son un rango válido que incluye al menos un edificio). También está garantizado que R-L+1 ≤ 1000
(es decir, todas las consultas tienen un rango que incluye máximo 1000
edificios).La salida debe tener exactamente C
líneas (una por consulta).
Para cada consulta, escribe el número del edificio más alto dentro del rango.
Si hay varios edificios empatados con la altura máxima dentro del rango, escoge el que está más a la izquierda entre ellos (es decir, el que tiene menor número).
8
3 5 2 6 1 4 7 2
3
2 5
0 7
4 4
3
6
4
La entrada nos da los 8
edificios mostrados en la primera imagen más arriba. Luego nos da 3 consultas:
L = 2
y R = 5
. Este es el ejemplo mostrado en la segunda imagen más arriba. El edificio más alto en este rango es el edificio número 3
que tiene altura 6
. La salida es el número de este edificio (3
).L = 0
y R = 7
. El rango incluye todos los edificios de la avenida. El edificio más alto de todos es el número 6
(con altura 7
).L = 4
y R = 4
. Este rango tiene sólo un edificio. El edificio más alto es ese mismo (porque es el único).5
1 2 1 2 1
3
0 4
0 2
2 4
1
1
3
La entrada nos da 5
edificios con alturas [1, 2, 1, 2, 1]
. Luego nos da 3 consultas:
L = 0
y R = 4
(todos los edificios). En este caso hay dos edificios empatados (el edificio número 1
y el edificio número 3
) porque ambos tienen altura 2
(la máxima posible en este caso). La salida debe ser el edificio que está más a la izquierda entre ellos (el edificio 1
).L = 0
y R = 2
. En este caso no hay empate porque el edificio 3
no está en el rango.L = 2
y R = 4
. En este caso tampoco hay empate.