该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

完美的石头

题目描述

Alice 有 $n$ 个格子，第 $i$ 个格子有 $a[i]$ 个宝石。

现在有 $m$ 个 Bob，每个 Bob 要一条宝石。

但是，对于第 $i$ 个 Bob，他只能拿到最前面 $l[i]$ 个格子和最后面 $r[i]$ 个格子的石头（$l[i]+r[i]<n$）。

现在，你想要知道，最优情况下有几个 Bob 可以拿到石头。

输入格式

第一行两个数 $n,m$。

接下来一行 $n$ 个数字，第 $i$ 个数字表示 $a[i]$。

接下来 $m$ 行，每行两个数字，第 $i$ 行表示 $l[i],r[i]$。

输出格式

一行一个数字表示答案。

样例

样例输入

3 3
1 1 1
1 1
1 1
1 1

样例输出

2

数据范围

对于第 $1-2$ 个测试点满足 $n,m\le 10$；

对于第 $3-7$ 个测试点满足 $n,m\le 20$；

对于第 $8-10$ 个测试点满足 $n,m\le 100$；

对于第 $11-13$ 个测试点满足 $n,m\le 1000$；

对于第 $14-20$ 个测试点满足 $n,m\le 300000$；

对于第 $14-17$ 个测试点额外满足 $\max(l[i])+\max(r[i])<n$。