Lava Jump 2

The study room at Gyeonggi Science High School sometimes fills with lava. Floating on the lava floor are $N$ platforms, numbered 1 through $N$. The position of platform $i$ is the integer $a_i$, and all positions are distinct. That is, $a_i \ne a_j$ for all integers $i$, $j$ with $1 \le i < j \le N$. The lava floor cannot be stepped on, only the platforms can. Unfortunately, once a platform is stepped on, it sinks below the lava forever as soon as the foot leaves it, and it can never be stepped on again.

Jeonghu wants to know how many ways his friend Ihwan can start from each platform, make zero or more jumps, and end on exactly one platform while every other platform has sunk. However, Ihwan jumps too far. Once he has jumped a distance $x$, every later jump must be at least $2x$. At first, he can jump any distance.

A jump from platform $i$ to platform $j$ has distance $|a_i - a_j|$. Two ways are different if the order in which the platforms sink is different. Platforms that are not stepped on do not sink. Position changes accumulate.

The first line contains two integers $N$ and $Q$, the number of platforms and the number of queries.

The second line contains $N$ integers separated by spaces. The $i$-th integer is $a_i$, the position of platform $i$.

Each of the next $Q$ lines contains two integers $b_i$ and $c_i$, meaning platform $b_i$ moves to position $c_i$.

On the first line, print the number of ways modulo $10^9 + 7$ in which Ihwan, starting from some platform, makes zero or more jumps and ends on exactly one platform while every other platform has sunk, summed over all starting platforms.

On each of the next $Q$ lines, print the same count after the $i$-th move.

• $1 \le N \le 40{,}000$
• $0 \le Q \le 40{,}000$
• $-10^{18} \le a_i, c_i \le 10^{18}$
• $1 \le b_i \le N$
• The platform positions are distinct at the start and after every query.
• All given numbers are integers.