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

佳圆（good）

题目描述

猪猪有一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。

对于每个 $1\le i\le n$，定义平面上的点 $P_i=(i,a_i)$。

对于一个下标 $k$，定义圆心 $W_k=(k,0)$，半径 $R_k=\vert a_k\vert$。由于 $P_k$ 到 $W_k$ 的距离恰好为 $R_k$，所以 $P_k$ 一定位于该圆上。

给定一个区间 $[l,r]$。若下标 $k$ 满足 $l\le k\le r$，并且：

• 对所有满足 $l\le i<k$ 的下标 $i$，点 $P_i$ 严格位于以 $W_k$ 为圆心、$R_k$ 为半径的圆内；
• 对所有满足 $k<i\le r$ 的下标 $i$，点 $P_i$ 严格位于以 $W_k$ 为圆心、$R_k$ 为半径的圆外；

则称 $k$ 是区间 $[l,r]$ 的一个佳点。

现在猪猪会给出 $q$ 次询问。对于每次询问给定的区间 $[l,r]$，你需要求出该区间内佳点的数量。

输入格式

第一行包含两个整数 $n,q$，分别表示序列长度和询问次数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行包含两个整数 $l,r$，表示一次询问的区间。

输出格式

输出 $q$ 行，第 $i$ 行输出一个整数，表示第 $i$ 次询问中区间 $[l,r]$ 内佳点的数量。

样例

样例输入 #1

5 6
1 3 1 4 2
1 5
1 3
2 5
3 5
2 4
1 1

样例输出 #1

1
1
0
1
1
1

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le n,q\le 2\times 10^5$，$-\!10^9\le a_i\le 10^9$，$1\le l\le r\le n$。

• 特殊性质 A：保证所有询问均满足 $l=1$。
• 特殊性质 B：保证所有询问均满足 $r=n$。
• 特殊性质 C：保证 $a_i\ge 0$。