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
2011-09-13 14:50:58 purav
is it guaranteed that A < B ?
2011-09-13 14:50:58 Buda IM (retired)
I agree with Ravi.
2011-09-13 14:50:58 Ravi Kiran
I think the problem is a simple excercise of RMQ and needs to be moved to tutorial, since we already have a lot at spoj, that test this idea.
2011-09-13 14:50:58 Alex Anderson
Hint:

What's probably confusing people is the slight ambiguity on inclusive/exclusive. The hill height of cityB is not included.

Last edit: 2011-05-27 18:36:14
2011-09-13 14:50:58 Ikhaduri
higher means <=,right?
2011-09-13 14:50:58 Anirban Saha
is it 2?
2011-09-13 14:50:58 [Retired] Fendy Kosnatha
what is answer for
5 2
4 4 4 4 4
3 5
4 1
2011-09-13 14:50:58 Anirban Saha
me too getting repeated wa's
2011-09-13 14:50:58 [Retired] Fendy Kosnatha
hai krzytof, can you tell me where is my mistake in this problem??
coz i think my code is right..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.