Chef and mountains
All submissions for this problem are available.
Chef is at a mountain range . There are N mountains lined up in a straight line . Each mountain has a height h[i] . Chef is currently at mountain a and wants to go to mountain b . He can do so by jumping from mountain a to b (he is talented ) . But he can jump from a to b only if there is no mountain between a and b whose height is strictly greater than that of mountain a .
In this problem , you will be given the array h containing heights of mountains and several queries with a and b , you will have you answer whether chef can jump from a to b or not .
The first line contains an integer N, the next line has N integers denoting the heights of the mountains h[i] . The next line has an integer Q , the number of queries , Then q lines follow each containing 2 integers a and b.
For each query , answer "YES" if chef can jump from a to b , otherwise answer "NO" if he cant .
- 1 <= N <= 105
- 1 <= h[i] <= 104
- 1 <= Q <= 105
- 1 <= a <= N
- 1 <= b <= N
Input: 5 2 3 1 2 4 3 1 3 2 5 2 3 Output: NO YES YES
For first query the answer is NO because between 1 and 3 , the second mountain is of height 3 which is more than height of mountain 1 which is 2 . For second query there is no mountain more than 3 units high between 2 and 5 so answer is YES. For 3rd query there is no mountain between 2 and 3 so the answer is YES .
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions