Description

王乐妍有 $n$ 个衣柜，第 $i$ 个格子有 $a_i$ 条裙子。

现在有 $m$ 个学妹，每个学妹要一条裙子。

但是，对于第 $i$ 个学妹 ，她只能拿到最前面 $l_i$ 个格子和最后面 $r_i$ 个衣柜的裙子 $(l_i + r_i<n)$

现在，你想要知道，最优情况下有几个学妹可以拿到裙子。

Format

Input

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

接下来一行 $n$ 个数字，第 $i$ 个数字表示 $a_i\ (0 \leqslant a_i \leqslant 10^9)$。

接下来 $m$ 行，每行两个数字，第 $i$ 行表示 $l_i,r_i$

Output

一行一个数字表示答案。

Samples

3 3
1 1 1
1 1
1 1
1 1

2

Limitation

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

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

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

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

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

对于第$14-17$ 个测试点额外满足 $\max(l_i)+\max(r_i)<n$