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
Explanation
Bob can catapult balls numbered 1 and 3.
hide comments
voidpoint11:
20240521 20:54:49
AC using Segment tree. Easy 

sxie12:
20220828 02:20:16
We allow B's hill to be higher than A's hill but not any hill between A and B. Kind of hard imagining how that works in practice. Last edit: 20220828 02:22:31 

idkreally:
20220603 22:05:24
AC using Sparse Table (0.05s) 

latecomer04:
20220307 14:24:44
straight forward segment tree question. 

rushi2001:
20210526 17:10:24
Very Easy Question


healthy567:
20210507 09:38:17
TOO EAsy 

cryp_bipul17:
20210427 11:25:28
Be alert handle the cases L<=B as well as B>A too


omharicu:
20210413 20:51:58
Missing testcases: 'NoneT


amantu_amir:
20210108 21:26:14
AC with Sparse Table. You can use Segment Tree or Binary Indexed Tree to solve this problem. 

baller_14:
20201027 05:13:07
AC using stack 
Added by:  Krzysztof Lewko 
Date:  20110525 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 