용암 점프 2

경기과학고등학교 학습실에는 때때로 용암이 찬다. 이 용암 바닥에는 1부터 $N$까지 번호가 매겨진 $N$개의 발판이 떠 있다. $i$번 발판의 위치는 정수 $a_i$로 나타내며, 발판의 위치는 모두 서로 다르다. 즉, $1 \le i < j \le N$인 정수 $i$, $j$에 대해 $a_i \ne a_j$이다. 용암 바닥은 밟을 수 없고 발판만 밟을 수 있다. 안타깝게도 한 번 밟은 발판은 발을 떼는 순간 용암 아래로 영원히 가라앉아, 다시 밟을 수 없다.

정후는 친구 이환이가 각 발판에서 출발해 0회 이상 점프하여, 마지막에 하나의 발판만 밟고 있고 나머지 발판은 모두 가라앉은 상태가 되는 경우의 수를 알고 싶어 한다. 다만 이환이는 과하게 뛴다. 한 번 거리 $x$만큼 뛴 뒤에는 그 이후의 점프 거리가 $2x$ 이상이어야 한다. 처음에는 어느 거리로 뛰어도 상관없다.

$i$번 발판에서 $j$번 발판으로 뛰는 거리는 $|a_i - a_j|$이다. 발판이 가라앉는 순서가 다르면 서로 다른 경우로 센다. 밟지 않은 발판은 가라앉지 않는다. 발판의 이동은 누적된다.

첫째 줄에 발판의 수 $N$과 쿼리의 개수 $Q$가 주어진다.

둘째 줄에 발판의 위치를 나타내는 $N$개의 정수가 공백으로 구분되어 주어진다. $i$번째 정수는 $i$번 발판의 위치 $a_i$이다.

다음 $Q$개의 줄에는 두 정수 $b_i$와 $c_i$가 각각 주어진다. 이는 $b_i$번 발판이 위치 $c_i$로 이동함을 뜻한다.

첫째 줄에 초기 상태에서, 이환이가 각 발판에서 출발해 0회 이상 점프하여 마지막에 하나의 발판만 밟고 있고 나머지 발판은 모두 가라앉은 상태가 되는 경우의 수의 합을 $10^9 + 7$로 나눈 나머지를 출력한다.

다음 $Q$개의 줄에는 $i$번째 이동 이후의 같은 경우의 수 합을 $10^9 + 7$로 나눈 나머지를 한 줄에 하나씩 출력한다.

• $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$
• 초기 상태와 매 쿼리 이후 발판의 위치는 서로 다르다.
• 주어지는 모든 수는 정수이다.