THRBL  Catapult that ball
Bob has unusual problem. In Byteland we can find a lot of hills and cities. King of Byteland ordered Bob to deliver magic balls from one city to another. Unfortunately, Bob has to deliver many magic balls, so walking with them would take too much time for him. Bob came up with great idea  catapulting them.
Byteland is divided into intervals. Each interval contains city and hill.
Bob can catapult magic ball accurately from city A to city B, if between them there isn't higher hill than A's hill.
Input
Every test case contains N and M (N<=50000) (M<=50000), number of intervals and number of balls.
In next line there's N numbers H(H<=10^9) separated by one space.
In next M lines numbers A and B (1<=A,B<=N), number of city from which we want to catapult the ball and number of city to which we want to catapult the ball.
Output
Write one number  number of magic balls that Bob can catapult successfully.
Example
Input:
7 3
2 3 5 4 2 1 6
3 5
2 5
4 6
Output:
2
Bob can catapult ball number 1 and 3.
hide comments
taponidhi:
20180920 16:03:47
Complexity can be O(n) for precomputation and O(1) for query.Just use NGE(Next Greater Element)(0.02 sec) concept.Its a wonderful problem to apply all ur range solving concepts.Make multiple submissions using different concepts.It gave me wonderful clarity and complexity difference idea. Last edit: 20180920 16:04:32 

m2do:
20180426 10:52:04
1. Sparse Tree = 0.04 secs...


lincolnbf:
20161011 03:17:03
binari, use segment tree. check online how to implement it. 

binari:
20160727 12:13:10
my code gives TLE, how could I optimize it, the code is so simple. Besides, every array element in given interval must be checked, so how could it be optimized? Last edit: 20160727 12:13:33 

try2catch:
20160404 08:52:31
Forget about [A,B) or (A,B) or[A,B], just take care of following points:


Daksh:
20150928 10:15:33
NGE .. :) 

Abhilash:
20150529 10:54:16
as its mentioned "between them", [A, B) works 

Malfple:
20141119 15:00:48
READ THE COMMENTS AND THE DESCRIPTION. The description said that there should be no hill higher than A's hill. so if B's hill > A's hill that's okay.


maniAC:
20140804 21:00:16
To AC this problem, you must read the comments T_T 

Alexandru Valeanu:
20130921 16:33:48
B is always lower than A and complexity for this problem I think is O(NlogN + M) 
Added by:  Krzysztof Lewko 
Date:  20110525 
Time limit:  0.156s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 