Sereja and Permutations

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Sereja has an array A of N integers: A[1], A[2], …, A[N]. Sereja also has an integer D.
Sereja calls a permutation P[1], P[2], …, P[N] as good if the following conditions hold.
A[P[1]] + D > A[P[2]],
A[P[2]] + D > A[P[3]],
⋮
A[P[N1]] + D > A[P[N]].
Sereja wants to sequentially perform M singleelement replacement operations on the array. Each of these operations consists of choosing an index p of the array, and replacing A[p] with a new value v. Your task is to keep track of the number of good permutations P[1], P[2], …, P[N] after each operation.
Input
The first line of input contains the integers N and D described above. The next line contains N integers A[1], A[2], …, A[N]. The line after this contains a single integer, M. Each of the next M lines contain two numbers p and v, implying that the new value of A[p] is v.Output
Output M lines. The i^{th} line should contain the number of good permutations modulo 10^{9} + 7 after we perform the i^{th} replacement operation.Constraints
 1 ≤ N, M ≤ 10^{5}
 1 ≤ A[i], v ≤ 10^{9}
 1 ≤ D ≤ 1000
 1 ≤ p ≤ N
Constraints
 Subtask #1 :N, M ≤ 10 (10 points)
 Subtask #2 :N, M ≤ 20 (10 points)
 Subtask #3: N, M ≤ 1000 (20 points)
 Subtask #4: original constrains (60 points)
Example
Input: 3 3 1 2 3 2 1 2 3 5 Output: 6 2
Explanation
Example case 1. After the first replacement operation, all permutations will be good. However, after the second operation, P[1] must be 3.
Author:  sereja 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/SEAPERMS 
Tags  feb16, mediumhard, sereja 
Date Added:  22112015 
Time Limit:  2  8 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 