4078 - Buyers Search

Created by Yonny Mondelo Hernández
Added by ymondelo20 (2018-09-05)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

There are N buyers standing in a line, conveniently numbered from 1 to N according to their position from left to right. Each buyer is willing to buy any house with a price less than or equal to a positive amount of money that he or she owns.

The C&N Company will sell H houses. For each house, a price P and a range (pair of values A and B) of positions are chosen, in order to determine who could be the potential buyer for that house. The potential buyer of a house will be the leftmost buyer with a position between A and B (both inclusive) that is willing to pay the price of that house (i.e. have an amount of money greater or equal to the amount needed for buying the house).

Given the amount of money that each buyer has, the price and the selected range of positions for every house, you have to find who is going to be the potential buyer of each house. Note that the amount of money of each buyer will not decrease in any way. C&N is just performing a study, in order to determine the best-selling prices for their houses.
;jsessionid=9F9AB116B2459A37235D0630E370CDE4
Hay N compradores de pie en una línea, convenientemente numerados del 1 al N según su posición de izquierda a derecha. Cada comprador está dispuesto a comprar cualquier casa con un precio menor o igual a una cantidad positiva de dinero que posee.

La compañía C&N venderá H casas. Para cada casa, se elige un precio P y un rango (par de valores A y B) de posiciones, a fin de determinar quién podría ser el comprador potencial de esa casa. El comprador potencial de una casa será el comprador más a la izquierda con una posición entre A y B (ambos inclusive) que está dispuesto a pagar el precio de esa casa (es decir, tiene una cantidad de dinero mayor o igual a la cantidad necesaria para comprar la casa).

Dada la cantidad de dinero que tiene cada comprador, el precio y el rango seleccionado de posiciones para cada casa, usted tiene que encontrar quién será el comprador potencial de cada casa. Tenga en cuenta que la cantidad de dinero de cada comprador no disminuirá de ninguna manera. C&N está realizando únicamente un estudio para determinar los mejores precios de venta para sus casas.
There are N buyers standing in a line, conveniently numbered from 1 to N according to their position from left to right. Each buyer is willing to buy any house with a price less than or equal to a positive amount of money that he or she owns.

The C&N Company will sell H houses. For each house, a price P and a range (pair of values A and B) of positions are chosen, in order to determine who could be the potential buyer for that house. The potential buyer of a house will be the leftmost buyer with a position between A and B (both inclusive) that is willing to pay the price of that house (i.e. have an amount of money greater or equal to the amount needed for buying the house).

Given the amount of money that each buyer has, the price and the selected range of positions for every house, you have to find who is going to be the potential buyer of each house. Note that the amount of money of each buyer will not decrease in any way. C&N is just performing a study, in order to determine the best-selling prices for their houses.
;jsessionid=9F9AB116B2459A37235D0630E370CDE4

Input specification

The first line will contain an integer N (1 N 105), representing the number of buyers. The second line will have N space-separated integer numbers Ci (1 Ci 106, for i between 1 and N) representing the amount of money of each buyer, from leftmost to rightmost. Next line will contain an integer H (1 H 105) representing the number of houses. And the following H lines will contain three space-separated integer numbers P (1 P 106), A and B (1 A B N), representing the price of a house and the selected range of positions for buyers.
La primera línea contendrá un entero N (1 ≤ N ≤ 10^5), que representa el número de compradores. La segunda línea tendrá N números enteros Ci (1 ≤ Ci ≤ 10^6, para i entre 1 y N) separados por un espacio que representan la cantidad de dinero de cada comprador, de izquierda a derecha. La siguiente línea contendrá un número entero H (1 ≤ H ≤ 10^5) que representa el número de casas. Y las siguientes líneas H contendrán tres números enteros separados por un espacio P ​​(1 ≤ P ≤ 10^6), A y B (1 ≤ A ≤ B ≤ N), que representan el precio de una casa y el rango seleccionado de posiciones para compradores.

The first line will contain an integer N (1 N 105), representing the number of buyers. The second line will have N space-separated integer numbers Ci (1 Ci 106, for i between 1 and N) representing the amount of money of each buyer, from leftmost to rightmost. Next line will contain an integer H (1 H 105) representing the number of houses. And the following H lines will contain three space-separated integer numbers P (1 P 106), A and B (1 A B N), representing the price of a house and the selected range of positions for buyers.

Output specification

You must output exactly H lines; the position of who will be the potential buyer of each house. Print -1 if, for some reason, there are no buyers in the selected range with enough money to afford the house.
Usted debe dar salida exactamente a las H líneas; en cada caso, con la posición de quien será el comprador potencial de cada casa. Imprima -1 si, por alguna razón, no hay compradores en el rango seleccionado con suficiente dinero para pagar la casa.

The first line will contain an integer N (1 N 105), representing the number of buyers. The second line will have N space-separated integer numbers Ci (1 Ci 106, for i between 1 and N) representing the amount of money of each buyer, from leftmost to rightmost. Next line will contain an integer H (1 H 105) representing the number of houses. And the following H lines will contain three space-separated integer numbers P (1 P 106), A and B (1 A B N), representing the price of a house and the selected range of positions for buyers.

Sample input

10
213 32 52 4524 4 445 565 45 45 199
5
10 1 10
343 5 8
5235 1 10
40 8 9
100 9 10

Sample output

1
6
-1
8
10

Hint(s)