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
Heitor Augusto [UFPB]: 2012-11-25 21:49:00

weak cases
7 3
2 -2 -1 -5 2 1 6
3 5
2 5
4 6

Choker: 2012-08-28 19:40:40

Thanks a lot RITESH

Sameer Jain: 2012-07-01 09:30:17

B is always higher than A

maaz: 2012-06-26 08:59:39

can A be higher than B ??

Ritesh Kumar Gupta: 2012-06-26 07:19:11

AT ALL,GUYS THERE IS AN AMBIGUITY IN THIS PROBLEM,PLEASE NOTE WE DON'T HAVE TO INCLUDE B WHILE MAKING QUERIES {[ Query(A,B-1)] is correct }.I got some 20 wrong answers because of this ..

berney: 2012-03-17 07:22:34

@Krzysztof Lewko : can you please check my solution(id 6670923)... I am getting WA..

Ekanda Susaptyo Hidayat: 2011-10-08 17:07:12

is it always B higher than A?

:D: 2011-10-02 16:54:27

It's because of problem update/modification.

sushil: 2011-10-02 15:41:39

Not related to the problem:
How can all the comments be at a same time "2011-09-13 16:50:58" ? Only my comment time is different.

Last edit: 2011-10-02 15:44:08
Krzysztof Lewko: 2011-09-13 14:50:58

@anubhav gupta, you have to check your segtree implementation, because your checking method is right.


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