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 ≤ 109) 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.


Added by:Krzysztof Lewko
Date:2011-05-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2019-05-23 10:42:11
sparse table - 0.02sec
2018-09-20 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: 2018-09-20 16:04:32
2018-04-26 10:52:04
1. Sparse Tree = 0.04 secs...
2. Segment Tree = 0.04 secs...
3. Square Root Decomposition = 0.11 secs...
2016-10-11 03:17:03
binari, use segment tree. check online how to implement it.
2016-07-27 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: 2016-07-27 12:13:33
2016-04-04 08:52:31
Forget about [A,B) or (A,B) or[A,B], just take care of following points:
1. if(B-A)<2 , then you know what will be the answer.
2. otherwise get answer of your query in range(A+1,B-1) and compare it with Array[A].
2015-09-28 10:15:33 Daksh
NGE .. :)
2015-05-29 10:54:16 Abhilash
as its mentioned "between them", [A, B) works
2014-11-19 15:00:48 Malfple
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.
Thanks for the comments... AC in one go ~~~{}
My complexity is O(N+M) No RMQ :P
I checked if B<A tho, just in case

Last edit: 2014-11-19 15:06:43
2014-08-04 21:00:16 maniAC
To AC this problem, you must read the comments T_T
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.