给定序列 $a_1,\dots,a_n$，共 $m$ 次操作，每次操作给出 $x,y,l,r$，将 $a_x$ 修改为 $y$，问修改前后，有几个区间 $[l',r']$ 满足 $l\le l'\le r'\le r$，且 $a_{l'},\dots,a_{r'}$ 的最大值发生了变化。

输入格式

第一行两个整数 $n,m$；

第二行 $n$ 个整数依次表示 $a_1,\dots,a_n$；

接下来 $m$ 行，每行四个整数 $x,y,l,r$ 表示一次操作。

输出格式

共 $m$ 行，依次表示每个操作的答案。

5 4
4 9 5 8 4
5 6 5 5
5 9 3 5
1 4 1 4
1 9 1 3

1
3
0
1

数据范围

对于 $25\%$ 的数据，满足 $n,m\le 300$。

对于另外 $25\%$ 的数据，满足 $n,m\le 5000$。

对于另外 $25\%$ 的数据，满足 $n,m\le 3\times 10^5$。

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$1\le a_i,y\le 10^9$，$1\le l\le x\le r\le n$。