Ancient Civilizations#5487
Petya has recently developed an interest in ancient civilizations. He discovered the birth and demise dates of different ancient civilizations in an encyclopedia and is now curious about the cultural influences these civilizations had on each other.
Petya assumes that there was a cultural exchange between two civilizations, and , if they coexisted for any non-zero period. For instance, if civilization began in BC and lasted until BC, and civilization started in BC and ended in BC, then they influenced each other culturally for years. Conversely, if civilization started in BC and lasted until BC, it could not have exchanged culture with civilization , but it did with civilization for years.
To advance his research, Petya wants to identify the pair of civilizations that had the shortest non-zero period of cultural exchange. Can you help him?
The first line of the input contains the integer , representing the number of civilizations Petya is interested in (1 \leq N \leq 100000). The following lines each describe a civilization with two integers, S_i and E_i, indicating the year of emergence and the year of demise, respectively. All numbers are within the absolute value of 10^9, and S_i < E_i.
Output two integers, representing the indices of the civilizations whose periods of existence have the smallest non-zero overlap. If no two civilizations overlap in time, output the single number .
Example 1