小红正在做一个计划，她先写了份初版方案，但是领导不太满意，让小红改一改。 

改着改着，小红就改了 16 版方案，然后领导说，还是用初版方案吧，现在小红非常的..... 

小红组内有 n 个人，大家合作完成了一个初版方案，初始时大家的愤怒值都是 0。 

但是领导对方案并不满意，共需要修改 m 次方案，每次修改会先让第 l 到 r 个人的愤怒值加 1，然后再修改方案。 

组内每个人都有一个愤怒阈值 a，一旦第 i 次修改时有人愤怒值大于愤怒闻值，他就会去找领导对线，直接将最终的方案定为第 i - 1 方案，并且接下来方案都不需要再修改了。 

小红想知道，最终会使用第几版方案。初版方案被认为是第 0 版方案。

第一行输入两个整数 n, m(1 <= n, m <= 10^5)表示数组长度和修改次数。 

第二行输入 n 个整数表示数组a(0 <= a <= 10^9) 

接下来 m 行，每行输入两个整数l, r(1 <= l <= r <= n)

2 3
2 2
1 1
1 2
2 2

3